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

Л. А. ОВЧАРОВ

ПРИКЛАДНЫЕ ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

И З Д А Т Е Л Ь С Т В О «М А Ш И Н О С Т Р О Е Н II Е»

Москва 1969

ПРЕДИСЛОВИЕ

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

Примерами таких задач могут служить задачи анализа рабо­ ты аэродрома, телефонного узла связи, морского порта, магазина, системы противовоздушной обороны (ПВО), многостаночного цеха и т. п. Общим для всех этих задач является необходимость количественного анализа процесса «обслуживания» различных заявок, например, самолетов, взлетающих с аэродрома и произ­ водящих на нем посадку; абонентов, обращающихся на автома­ тическую телефонную станцию (АТС) для соединения с другими абонентами; судов, прибывающих в порт для разгрузки и погруз­ ки; покупателей, обращающихся в магазин за покупками; само­ летов, обстреливаемых системой ПВО, и т. д. Заявки поступают на обслуживание в различные, вообще случайные моменты вре­ мени, образуя так называемый «поток заявок». Потоки заявок могут иметь различную структуру и интенсивность (частоту по­ ступления заявок). Следовательно, для решения задач теории массового обслуживания нужно прежде всего уметь анализиро* вать потоки заявок. В первой главе книги рассматриваются раз­ личные потоки и проводится исследование основных характери­ стик этих потоков. Так как заявки следуют друг за другом в случайные моменты времени, то для анализа потоков заявок широко привлекается аппарат теории вероятностей.

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

3

состояния в другое. Например, при работе автоматической теле­ фонной станции она может быть некоторое время занята, а в другое время — свободна. Если АТС занята, а в этот момент абонент обращается с вызовом, то он получает отказ (в трубке частые гудки — «занято»). При анализе таких случайных процес­ сов в книге широко применяется новый методический прием, в основу которого положено составление «размеченного графа состояний» (гл. 2). Применение размеченных графов состояний облегчает математическое исследование случайных процессов и делает его более наглядным.

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

Сама система массового обслуживания можег состоять из од­ ного или нескольких каналов обслуживания. Например, если рас­ сматривать работу аэродрома с одной взлетно-посадочной поло­ сой (ВПП), то можно считать, что мы имеем дело с одноканаль­ ной системой массового обслуживания. Если рассматривается работа морского порта с п причалами, где производится разгруз­

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

Работа каждого канала обслуживания носит, как правило, случайный характер. Например, при анализе работы морского порта время разгрузки и погрузки судна зависит от различных причин: вида груза, его количества, квалификации портовых ра­ бочих и т. п. Поэтому время обслуживания каждой заявки будет случайным.

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

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

4

Глава 1

ПОТОКИ СОБЫТИЙ

§ 1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Потоком событий называется последовательность событий,

происходящих одно за другим в какие-то случайные моменты времени. Примерами могут служить: поток вызовов, поступаю­ щих на АТС; поток изготовленных деталей, поступающих в ОТК завода; поток машин, нуждающихся в заправке горючим; поток самолетов, приземляющихся в данном аэропорту; поток заби­ тых в ворота шайб при игре в хоккей и т. п. Различают потоки о д н о р о д н ы х и н е о д н о р о д н ы х событий. Например, по­ ток самолетов, приземляющихся на аэродроме, будет однород­ ным, если не различать самолеты по типам. Если же мы будем различать типы самолетов (ТУ-104, ИЛ-18 и т. д.), тот же поток будет уже неоднородным. В дальнейшем будем рассматривать главным образом потоки од­ нородных событий. События

последовательность точек t\y U, ... на числовой оси 01, соответст­

вующих моментам появления событий (рис. 1.1.1).

Потоки событий различаются по своей внутренней структуре. Самым простым потоком с точки зрения его построения является «регулярный поток». Регулярным потоком называется поток, в

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

Рассмотрим поток, в котором события разделены интервала­ ми времени Ти Г2, (рис. 1.1.2.). Эти интервалы вообще являются

7

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

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

менту времени t, попадет больше одного события (P>j(/, At)).

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

(Pl (t, At)):

Так как для любого интервала At

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

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

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

Стационарным потоком событий называется поток, для кото­

рого вероятность появления того или другого числа событий на

8

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

Рассмотрим на оси 0/ ординарный поток событий и найдем среднее число событий, наступающих на интервале времени Д/,

функцией времени. Она имеет размерность, обратную размерно­ сти времени [~7"j Д л я CTai*H0HaPH0r0 потока его интенсив­

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

Х(/) = Х= const.

§ 1.2. ЗАКОН РАСПРЕДЕЛЕНИЯ УЧАСТКА ВРЕМЕНИ, НА КОТОРЫЙ ПАДАЕТ ТОЧКА

В этом параграфе будет рассмотрена внутренняя структура одного частного вида стационарного потока Пальма, у которого все интервалы между соседними событиями взаимно независи­ мы и распределены одинаково с функцией распределения F(t) *.

Пусть имеется стационарный поток Пальма (рис. 1.2.1), изо­ браженный на оси Of. Допустим, что на эту ось падает случайным образом точка S, отмеченная на рис. 1.2.2 крестом, причем поло­

жение точки S никакие связано с моментами появления событий.

* Такие потоки иногда называют рекуррентными.

9

Требуется определить закон распределения того участка Г*, на который упала точка 5.

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

распределения интервала времени Г* между появлением двух автобусов, на котором появился пассажир (на который упала точка S), в общем случае не совпадает с законом F(t). Этот на

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

Допустим, что интервал времени Т (в часах) между появле­

нибудь момент времени. Что вероятнее — что он попадет на уча­ сток длины 0,8 или на участок длины 0,2? Очевидно, первое более вероятно: отрезков 0,8 и 0,2 на оси 0£ в среднем одинаковое коли­ чество, но отрезок 0,8 длиннее в 4 раза, значит, отрезки 0,8 зани­ мают на оси в среднем в 4 раза большую протяженность, чем отрезки 0,2; следовательно, вероятность попадания точки 5 на отрезок 0,8 равна уже не 0,5, а 0,8, а вероятность попадания на отрезок 0,2 равна 0,2. На этом простом примере можно убедиться в том, что закон распределения того промежутка, на который попала точка S, в общем случае не совпадает с его априорным

законом распределения.

Решим эту же задачу в общем виде. Пусть априорная функ­ ция распределения случайной величины Г-интервала между двумя соседними событиями есть F(t), а плотность распределе­ ния f (t) (если случайная величина Т является дискретной слу­

чайной величиной, то плотность распределения может быть вы-

10