Примеры систем массового обслуживания. Анализ задач ТСМО
Пример 1. Телефонная связь времен Эрланга представляла себой телефонную станцию, связанную с большим числом абонентов. Телефонистки станции по мере поступления вызовов соединяли телефонные номера между собой.
Задача: Какое количество телефонисток (при условии их полной занятости) должно работать на станции для того, чтобы потери требований были минимальными.
Пример 2. Система скорой помощи некоего городского района представляет собой пункт (который принимает требования на выполнение), некоторое количество автомашин скорой помощи и несколько врачебных бригад.
Задача: Определить количество врачей, вспомогательного персонала, автомашин, для того чтобы время ожидания вызова было для больных оптимальным при условии минимизации затрат на эксплуатацию системы и максимизации качества обслуживания.
Пример 3. Важной задачей является организация морских и речных перевозок грузов. При этом особое значение имеют оптимальное использование судов и портовых сооружений.
Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.
Пример 4. Система обработки информации содержит мультиплексный канал и несколько ЭВМ. Сигналы от датчиков поступают на мультиплексный канал, где буферизуются и предварительно обрабатываются. Затем поступают в ту ЭВМ, где очередь минимальна.
Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.
Пример 5. На рис 3.1. изображена структурная схема типичной системы массового обслуживания – ремонтного предприятия (например, по ремонту ПЭВМ). Порядок ее работы ясен из схемы и не требует разъяснений.
Рис 3.1.
Нетрудно привести множество других примеров из самых различных областей деятельности.
Характерным для таких задач является:
1. Условия “двойной” случайности –
o случаен момент времени поступления заказа на обслуживание (на телефонную станцию, на пункт скорой помощи, на вход процессора, случаен момент времени прибытия морского судна под погрузку и т.д.);
o случайна длительность времени обслуживания.
2. Проблема бича нашего времени – очередей: судов перед шлюзами, машин перед прилавками, задач на входе процессоров вычислительного комплекса и т.д.
А.К. Эрланг обратил внимание на то, что СМО могут быть разделены на два типа, а именно: на системы с ожиданием и системы с потерями. В первом случае – заявка, поступившая на вход системы “ждет” очереди на выполнение, во втором – она из-за занятости канала обслуживания получает отказ и теряется для СМО.
В дальнейшем мы увидим, что к классическим задачам Эрланга прибавляются новые задачи:
a. требования на обслуживание принимаются до тех пор, пока очередь не достигнет заданного размера;
b. требования остаются в очереди, но ожидают обслуживания не более заданного времени tож, после чего из очереди исключаются;
c. время ожидания обслуживания и время самого обслуживания ограничивается некоторой величиной t S = tож + tобсл и т.д.
Реальные системы, с которыми приходится иметь дело на практике, как правило, очень сложны и включают в себя ряд этапов (стадий) обслуживания (рис 1.1.). Причем на каждом этапе может существовать вероятность отказа в выполнении или существует ситуация приоритетного обслуживания по отношению к другим требованиям. При этом отдельные звенья обслуживания могут прекратить свою работу (для ремонта, наладки и т.д.) или могут быть подключены дополнительные средства. Могут быть такие обстоятельства, когда требования, получившие отказ, вновь возвращаются в систему (подобное может происходить в информационных системах).
Понятия, определения, терминология
Все СМО имеют вполне определенную структуру, изображенную на рис 3.2
Рис 3.2
Определения, термины
o Потоком называют последовательность событий. Поток, состоящий из требований на обслуживание, называют потоком требований.
o Поток требований, поступающих в обслуживающую систему, называют входящим потоком.
o Поток требований, которые обслужены, называют выходящим потоком.
o Совокупность очередей и приборов (каналов) обслуживания называются системой обслуживания.
o Каждые требования поступают на свой канал, где подвергается операции обслуживания.
o Каждая СМО имеет определенные правила формирования очереди и правила или дисциплину обслуживания.
Классификация СМО
3.1.4.1. По характеру источника требований различают СМО с конечным и бесконечным количеством требований на входе.
В первом случае в системе циркулирует конечное, обычно постоянное количество требований, которые после завершения обслуживания возвращаются в источник.
Во втором случае источник генерирует бесконечное число требований.
Пример 1. Цех с постоянным количеством станков или определенное количество ПЭВМ в терминальном классе, требующих постоянного профилактического осмотра и ремонта.
Пример 2. Сеть Internet с бесконечным требованием на входе, любой магазин, парикмахерская и т.д.
Первый вид СМО называют замкнутой, второй – разомкнутой.
СМО различают:
3.1.4.2. По дисциплине обслуживания:
a. обслуживание в порядке поступления;
b. обслуживание в случайном порядке (в соответствии с заданным законом распределения);
c. обслуживание с приоритетом.
3.1.4.3. по характеру организации:
a. с отказами;
b. с ожиданиями;
c. с ограниченным ожиданием.
В первом случае заявка получает отказ, когда канал занят. Во втором случае – ставится в очередь и ждет освобождения канала. В третьем случае вводится ограничения на длительность ожидания.
3.1.4.4. По количеству единиц обслуживания:
a. одноканальные;
b. двухканальные;
c. многоканальные.
3.1.4.5. По числу этапов (фаз) обслуживания - на однофазные и многофазные. (Примером многофазных СМО может служить любая поточная линия).
3.1.4.6. По свойствам каналов: на однородные, когда каналы имеют одинаковую характеристику и неоднородные в противном случае.
Основная задача ТСМО
Основная задача ТСМО заключается в установлении зависимости между характером потока заявок на входе СМО, производительностью одного канала, числом каналов и эффективностью обслуживания.
В качестве критерия эффективности могут быть использованы различные функции и величины:
o среднее время простоя системы;
o среднее время ожидания в очереди;
o закон распределения длительности ожидания требования в очереди;
o средний % заявок, получивших отказ; и т.д.
Выбор критерия зависит от вида системы. Например, для систем с отказами главной характеристикой является абсолютная пропускная способность СМО; менее важные критерии - число занятых каналов, среднее относительное время простоя одного канала и системы в целом.Для систем без потерь(с неограниченным ожиданием) важнейшим является среднее время простоя в очереди, среднее число требований в очереди, среднее время пребывания требований в системе, коэффициент простоя и коэффициент загрузки обслуживающей системы.
Современная ТСМО является совокупностью аналитических методов исследования перечисленных разновидностей СМО. В дальнейшем из всех достаточно сложных и интересных методов решения задач массового обслуживания будут изложены методы, описываемые в классе марковских процессов типа “гибель и размножение”. Это объясняется тем, что именно эти методы чаще всего используются в практике инженерных расчетов.