3. Задачи массового обслуживания

Возникают, когда имеет место поток заявок, требований или клиентов, нуждающихся в обслуживании. В общем случае заявки приходят через случайные промежутки времени и продолжительность обслуживания одной заявки также случайна. Системы, занятые обслуживанием таких потоков, называют системами массового обслуживания (СМО). Обычно в СМО выделяют 4 составляющих:

1. поток заявок (входящий поток),

2. очередь заявок,

3. обслуживающие устройства,

4. выходящий поток.

В СМО может возникать как очередь заявок на обслуживание, так и очередь обслуживающих устройств (простои). С любой очередью связаны потери.

Различают СМО

1. с отказами, когда при занятых устройствах пришедшая в систему заявка получает отказ и, следовательно, очереди заявок быть не может,

2. с ожиданием (с очередью), когда при занятых устройствах обслуживания заявка встает в очередь и ожидает обслуживания.

Для описания процессов, протекающих в СМО применяют вероятностные модели. В качестве показателей эффективности могут использоваться вероятность отказа, средняя длина очереди, среднее время пребывания заявки в системе, пропускная способность и др.

Задача массового обслуживания состоит в определении оптимальной структуры и оптимальных параметров СМО.

Задачи массового обслуживания особенно характерны для сферы услуг и производства. Примерами могут служить задачи организации торговли, медицинского обслуживания, ремонта, серийного и массового производства, работы вычислительного центра и отдельной ЭВМ в многозадачном и многопользовательском режимах и т.п.

4. Задачи выбора маршрута

В зависимости от вида искомого маршрута различают два варианта задач.

1. Задача о кратчайшем пути. Между двумя заданными пунктами или узлами имеется конечное множество путей, состоящих из переходов (дуг), соединяющих промежуточные пункты. Один переход может входить более чем в один путь. Каждый переход имеет свой критерий (время, длина, стоимость). Требуется найти путь, кратчайший в смысле принятого критерия.

Искомый путь является незамкнутым, прохождение всех промежуточных пунктов не требуется. При детерминированных показателях используется детерминированная модель, а при случайных показателях – вероятностная модель.

Такие задачи возникают при прокладке маршрутов различных транспортных средств, трасс дорог, трубопроводов и т.д.

2. Задача коммивояжера. Коммивояжер, выйдя из своего города, должен обойти все города, входящие в сферу обслуживания фирмы, и вернуться обратно. При этом каждый город посещается один раз. Известны показатели переходов между всеми парами городов. Требуется найти маршрут, обеспечивающий минимальные затраты времени, расход горючего или стоимость проезда. Искомый маршрут замкнутый, прохождения всех пунктов обязательно.

5. Задачи замены оборудования

В зависимости от типа оборудования различают два вида задач замены.

1. Оборудование рассматривается как единое целое, характеристики которого с течением времени ухудшаются. В результате снижается производительность, качество выполнения операций, возрастают затраты на эксплуатацию и текущие ремонты.

С увеличением частоты замены оборудования все эти показатели будут улучшаться, но одновременно будут резко возрастать затраты на монтаж нового оборудования. Необходимо определить моменты замены оборудования, наилучшие в смысле выбранного критерия. В качестве критерия часто рассматривается прибыль, получаемая на оборудовании за определенный период времени. К оборудованию в данном случае можно отнести обрабатывающий центр, самолет, локомотив и т.п.

2. Оборудование состоит из большого числа относительно недорогих элементов, которые могут внезапно полностью выходить из строя.

Моменты выхода из строя случайны. Примерами подобного оборудования могут служить электронные системы, компьютеры и др. Здесь наряду с моментами замены нужно определять и уровень, на котором следует проводить замену. Можно заменять отдельный элемент, плату, узел или целый блок. При этом, если уменьшается время на замену, то растет стоимость заменяющих частей и наоборот. Для математического описания подобных задач используются в основном вероятностные модели.