Глава 10. Теория очередей

Математика подобна мясорубке, она может

переработать любое мясо, но для того, чтобы

получить хорошие котлеты, нужно и хорошее мясо.

Гексли

Один воин вышел из города и проходил по 12 верст в день, а другой вышел одновременно и шел так: в первый день прошел 1 версту, во второй день 2 версты, в третий день 3 версты, в четвертый 4 версты, в пятый 5 верст и так прибавлял каждый день по версте, пока не настиг первого. Через сколько дней второй воин настигнет первого?

Старинная задача

Основные понятия теории очередей

Многие экономические задачи связаны с системами массового обслуживания, в которых происходит удовлетво­рение требований на выполне­ние каких–либо услуг.

Исследованием систем массового обслуживания занимается теория очередей, на начальное развитие которой оказали особое влияние труды датского ученого Эрланга А.К. (1878–1929) в области проектирования и эксплуатации телефонных станций.

Общая схема системы массового обслуживания показана на рис. 11.1.

Рис. 10.1.

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

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

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

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

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

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

Простейший поток событий обладает тремя свойствами:

- стационарностью – постоянным количеством событий в единицу времени;

- отсутствием последействия – независимостью количества событий после любого момента времени от количества событий до него;

- ординарностью – практической невозможностью одновременного поступления нескольких требований.

Для простейшего потока частота наступления событий подчиняется закону Пуассона, то есть вероятность того, что за время t произойдет k событий определится

где l – количество событий в единицу времени (интенсивность потока).

Вероятность выхода из строя одной установки (k = 1) при отказе в среднем в единицу времени двух установок (l = 2)

Вероятность отсутствия вышедших из строя установок за любой случайный час – 13%, вероятность выхода из строя одной установки – 27%, двух – 27%, трех – 18%, четырех – 9% и т.д. (рис. 1.2).

Рис. 10.2. Распределение Пуассона для l = 2

По теореме сложения вероятностей вероятность суммы независимых событий равна сумме вероятностей этих событий, отсюда вероятность отказа в единицу времени не более четырех установок равна сумме вероятности отсутствия отказа и вероятностей отказа одной, двух, трех, четырех установок:

Вероятность отказа более четырех установок

P (m >4) = 1– 0,945 = 0,055.

Дисциплина очереди описывает порядок обслуживания требований в системе. Длина очереди может быть ограниченной или неограниченной. Правила постановки в очередь: FIFO – «первым пришел первым обслуживаешься», LIFO – «последним пришел первым обслуживаешься», по другим приоритетам или случайно.

Механизм обслуживания характеризуется продолжительностью процедур обслуживания и количеством одновременно обслуживаемых требований.

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

Вероятность того, что время обслуживания не превосходит не­которой величины t, определяется формулой:

.

где m – величина, обратная среднему времени обслужи­вания:

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

,

где l – среднее число требований, поступающих в единицу времени; m – среднее число требований, удовлетворяемых в единицу времени; Т_обс – среднее время обслуживания одним каналом одного требования.

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

Различают следующие виды систем массового обслуживания.

В зависимости от условий ожидания требованием начала об­служивания различают системы массового обслуживания с отказами и с ожиданием.

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

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

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

Системы, допускающие очередь, но с ограниченным сроком пребы­вания каждого требования в ней, называются системами с ограни­ченным временем ожидания.

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

По числу каналов обслуживания различают одноканальные и многоканальные системы.

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