Системы массового обслуживания с приоритетами

-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ	3
1. КЛАССИФИКАЦИЯ СМО	4
2. ОСНОВНЫЕ ЭЛЕМЕНТЫ  СМО И ЕЕ ХАРАКТЕРИСТИКИ	6
3. СХЕМЫ СИСТЕМ МАССОВОГО  ОБСЛУЖИВАНИЯ	11
3.1. ОДНОКАНАЛЬНАЯ СМО  С ОТКАЗАМИ	11
3.2. МНОГОКАНАЛЬНАЯ СМО  С ОТКАЗАМИ	12
3.3. ОДНОКАНАЛЬНАЯ СМО  С ОЖИДАНИЕМ	13
3.4. ДРУГИЕ РАЗНОВИДНОСТИ  СМО	15
4. ТРУДНОСТИ,   ВОЗНИКАЮЩИЕ   ПРИ    МОДЕЛИРОВАНИИ СИСТЕМЫ  МАССОВОГО  ОБСЛУЖИВАНИЯ	16
4.1. ТРУДНОСТИ   МАТЕМАТИЧЕСКОГО   ОПИСАНИЯ   СИСТЕМ МАССОВОГО  ОБСЛУЖИВАНИЯ	16
4.2. ГИБКОСТЬ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ОБСЛУЖИВАНИЯ	18
4.3. ПОДГОТОВКА ИСХОДНЫХ  ДАННЫХ  И ПРОВЕРКА СТАТИСТИЧЕСКИХ  ГИПОТЕЗ	20
5. ПРИНЯТИЕ РЕШЕНИЙ  С ИСПОЛЬЗОВАНИЕМ МОДЕЛЕЙ МАССОВОГО  ОБСЛУЖИВАНИЯ	21
5.1. МОДЕЛИ СО СТОИМОСТНЫМИ  ХАРАКТЕРИСТИКАМИ	21
5.2. ОПТИМАЛЬНАЯ СКОРОСТЬ ОБСЛУЖИВАНИЯ μ	23
5.3. ОПТИМАЛЬНОЕ ЧИСЛО  ОБСЛУЖИВАЮЩИХ ПРИБОРОВ	24
5.4. МОДЕЛИРОВАНИЕ С  УЧЕТОМ ПРЕДПОЧТИТЕЛЬНОСТИ УРОВНЯ  ОБСЛУЖИВАНИЯ	25
ЗАКЛЮЧЕНИЕ	27
ЛИТЕРАТУРА	30

 

 

 

 

 

И грозной цепью сил природы

Весь мир таинственно  объят.

И. Гете

 

ВВЕДЕНИЕ

 

«Предложен метод оптимизации затрат на содержание ремонтно-восстановительных служб нефтегазодобывающих предприятий на основе теории массового обслуживания. Простой аналитический вид расчетных соотношений и позволяет оперативно рассчитывать оптимальные затраты с учетом динамики цен на нефть и характеристик фонда скважин нефтедобывающего предприятия¹…» Новости, подобные этой, различные исследования, программные разработки стали часто появляться в последние десятилетия по мере того, как компьютеры становились доступнее, мощнее и распространеннее.

Но что же на самом деле скрывается за аббревиатурой «Теория массового  обслуживания» и почему идеи данной теории активно используются в различных  областях? Цель данной работы ответить на этот вопрос, а также осветить проблемы, связанные и практическим использованием СМО.

Попытаемся задуматься над некоторыми ситуациями, с которыми довольно часто приходится сталкиваться. Например, представим себе:

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

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

Встречающийся на каждом шагу «феномен» ожидания является прямым следствием вероятностного характера  возникновения потребностей в том или ином виде обслуживания и разброса показателей соответствующих обслуживающих систем. Действительно, ни время возникновения потребности в обслуживании, ни продолжительность обслуживания поступившего в обслуживающую систему клиента, как правило, заранее не известны. В противном случае режим работы обслуживающей системы можно было бы регламентировать таким образом, чтобы полностью исключить эту неприятную необходимость «ждать». [2] Изучением таких ситуаций занимается теория массового обслуживания.

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

Теория массового обслуживания появилась в связи с задачами организации телефонной связи. Ее родоначальником  явился датский инженер А. К. Эрланг (1878-1929), первые публикации которого относятся  к 1920-м годам. В 1940-1950-ч годах теория получила развитие в работах К. Пальма (Швеция), Ф. Паллачека (Франция), А. Я. Хинчина и Б. В. Гнеденко (СССР). Термит «теория массового обслуживания» ввел А. Я. Хинчин. На английском языке используется термин «queuing theory», в прямом переводе «теория очередей». По существу теория массового обслуживания – это ветвь теории вероятности, а точнее, ее раздела «случайные процессы». [7]

В теории систем массового  обслуживания (СМО) обслуживаемый объект называют требованием².

Средства, обслуживающие требования, называются обслуживающими устройствами или каналами обслуживания. Например, к ним относятся каналы телефонной связи, посадочные полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.

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

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

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

Рассмотрим пример из практической деятельности: у интернет-газеты в повседневной, вялотекущей жизни  сформирован круг постоянных читателей, которые периодически узнают новости, читают статьи, посылая запросы к серверу редакции (также как почтальон приносит нам домой каждый день выписанную нами газету). Но во время чрезвычайного происшествия (например, когда обвалилась крыша аквапарка или были взяты заложники во время мюзикла, или произошел теракт) новость о случившемся бумажные периодические издания могут сообщить только на следующее утро (когда нам опять же газету принесет почтальон), телевидение – через пару часов, когда будет готов репортаж. А прочитать о случившемся в интернет-газете можно будет буквально через несколько минут, после поступления информации о происшествии. Следовательно, большое количество людей, которые захотят узнать подробности будут обращаться к интернет-газете. Таким образом, количество запросов резко возрастет³, сервер может не справиться с таким потоком информации и либо сервер отключают из-за перегрузки, либо придется очень долго ждать пользователю, когда сервер обработает его запрос. Для избежания такой ситуации, необходимо чтобы, к примеру, запросы пользователей обрабатывало два или больше серверов. Но тут же возникает вопрос: сколько их необходимо? Конечно, можно сказать, что чем больше, тем лучше! Но данный принцип действителен только тогда, когда тебе что-то достается просто так, а не стоит приличных денег. Вот и возникает вопрос об оптимальном количестве обрабатывающих сервисов.

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

 

1. КЛАССИФИКАЦИЯ СМО

 

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

СМО может классифицироваться по следующим признакам:

• Число каналов обслуживания
• Поведение заявки
• Структура очереди
• Число этапов обслуживания
• и др.

Одна из классификаций СМО представлена ниже.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. ОСНОВНЫЕ ЭЛЕМЕНТЫ СМО И ЕЕ ХАРАКТЕРИСТИКИ

 

Прежде чем рассматривать  элементы СМО введем вначале обозначения, которые представляются наиболее подходящими  для систем массового обслуживания с входным и выходным потоками [2]:

(a/b/c) : (d/e/f),

где символы a, b, c, d, e и f ассоциированы с конкретными наиболее существенными элементами модельного представления процессов массового обслуживания⁴ и интерпретируются следующим образом:

a – распределение моментов поступления заявок на обслуживание;

b – распределение времени обслуживания (или выбытий обслуженных клиентов);

с – число параллельно  функционирующих узлов обслуживания

d – дисциплина очереди

e – максимальное число допускаемых в систему требований (число требований в очереди + число требований принятых на обслуживание)

f – емкость источника, генерирующего заявки на обслуживание.

Для конкретизации a и b приняты следующие стандартные обозначения:

M – Пуассоновское (или Марковские) распределение моментов поступления заявок на обслуживание или выбытий из системы обслуженных клиентов (или экспоненциальное распределение интервалов времени между моментами последовательных поступлений или продолжительностей обслуживания клиентов);

D – фиксированный (детерминированный) интервал времени между моментами последовательных поступлений в систему заявок на обслуживание или детерминированная (фиксированная) продолжительность обслуживания;

E_k – распределение Эрланга или гамма-распределение интервалов времени между моментами последовательных поступлений требований в обслуживающую систему или продолжительностей обслуживания (при этом под k понимается параметр распределения);

GI – распределение произвольного вида моментов поступления в систему заявок на обслуживание (или интервалов времени между последовательными поступлениями требований);

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

При анализе введенных  обозначений можно выявить следующие  основные элементы СМО:

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

Становиться очевидно, что  система обслуживания считается  заданной, если известны:

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

Следовательно, изучение СМО начинается с анализа входящего потока требований.

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

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

Среднее число требований, поступающих  в систему обслуживания за единицу  времени, называется интенсивностью поступления требований и определяется следующим соотношением:

где Т – среднее значение интервала между поступлением очередных требований.[5]

Для многих реальных процессов  поток требований достаточно хорошо описывается законом распределения Пуассона. Такой поток называется простейшим.