Экономико-математическое моделирование : Модели массвого обслуживания

Модели массвого обслуживания

Факультет информационных технологий

Кафедра высшей математики и кибернетики

Дисциплина «Модели и методы управления»

СРС

Модели массового обслуживания

Выполнила: Ахметова Д, ФИТ(АиУ), 3 курс

Проверил: Амиргалиев Е.Н

Алматы 2010

Содержание

Введение

1 Классификация моделей массового обслуживания

2 Распределение вероятностей для длительности интервалов между последовательными поступлениями требований на обслуживание

3 Распределение вероятностей для длительностей обслуживания

4 Одноканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания

5 Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания

6 Процессы рождения и гибели

7 О других методах массового обслуживания

Введение

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

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

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

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

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

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

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

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

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

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

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

1 Классификация моделей массового обслуживания

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

1) входной поток, т. е. поток поступающих требований или заявок на обслуживание;

2) дисциплину очереди;

3) механизм обслуживания.

Входной поток.

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

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

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

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

Дисциплина очереди.

Данная характеристика позволяет описать порядок обслуживания требований, поступающих на вход системы. Чаще всего используется дисциплина очереди типа: первым пришел-первым обслуживаешься. Такой порядок обслуживания с точки зрения математического моделирования является наиболее простым; следует также заметить, что он имеет отношение лишь к таким ситуациям, когда требования в ожидании обслуживания выстраиваются в ряд. Читателю из его личного опыта известно, что возможны многочисленные виды дисциплины очереди, отличающиеся от упомянутой выше. Иногда используется дисциплина «пришел последним- обслуживаешься первым». Посмотрите, например, что происходит, когда вы входите первым в совершенно пустой лифт на одном из верхних этажей многоэтажного здания: по мере того как лифт начинает спускаться, он заполняется теми, кто вошел в него позднее. Дисциплину очереди в данной ситуации вполне можно отнести к типу «пришел последним -- обслуживаешься первым», если обслуживание связать с очередностью вашего выхода из лифта, когда он прибывает на первый этаж. В некоторых случаях порядок обслуживания является фактически случайным. Он часто практикуется, например, школьными учителями при опросе учеников. Иногда дисциплина очереди строится по некоторой системе приоритетов (так, например, в случае, когда принимаются меры по спасению пассажиров тонущего корабля, в спасательные шлюпки первыми сажают женщин и детей). Наконец, по тем или иным соображениям клиент может отказаться от ожидания и принять решение покинуть очередь до того, как его успеют обслужить (т. е. имеет место очередь с ограниченным временем ожидания поступающих требований).

Механизм обслуживания.

Обслуживающий механизм аналогично входному потоку требований характеризуется продолжительностью процедур обслуживания и количеством требований, удовлетворяемых в результате выполнения каждой такой процедуры. В приведенном выше примере, где речь шла об обслуживании клиентов в парикмахерской или в ресторане, процедура обслуживания считается завершенной, когда клиент (а в случае обслуживания в ресторане, возможно, и целая группа клиентов) покидает соответствующее заведение после предоставления ему услуг. Продолжительность интервала времени, требуемого для реализации процедуры обслуживания, частично зависит от запросов клиента (или группы клиентов). Но она может зависеть также и от состояния самой обслуживающей системы; так, например, обслуживающий персонал может форсировать процедуры обслуживания, если обслуживание ожидает большое число клиентов. Как и продолжительности интервалов между поступлениями требований, длительности обслуживания в каждой из обслуживающих точек могут (хотя это и не обязательно) описываться с помощью независимых случайных переменных с идентичными распределениями вероятностей их численных значений. В ряде случаев приходится также учитывать вероятность выхода обслуживающего прибора из строя по истечении некоторого ограниченного интервала времени. Для описания механизма обслуживания требуется также указать количество и взаимное расположение обслуживающих приборов или каналов. Так, например, прилетев из Нью-Йорка в аэропорт Лондона, пассажир должен пройти там так называемую паспортную проверку. При этом все пассажиры выстраиваются в одну линию и каждый из дождавшихся своей очереди пассажиров направляется к одному из освободившихся чиновников, производящих проверку паспорта. Совершенно иная картина наблюдается, например, в часы пик в банке, когда очереди образуются ко всем без исключения кассирам. В этом случае посетитель должен выбрать одну из очередей и ожидать обслуживания со стороны вполне определенного кассира. Если ваш выбор оказался неудачным, пребывание в очереди может отнять у вас даже больше времени, чем у некоторых из пришедших после вас, которым посчастливилось стать в более «быстрые» очереди. (Если очереди не слишком велики, можно схитрить, перейдя от выбранного вначале окна к другому, возле которого очередь стала короче.)

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

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

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

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

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

2 Распределение вероятностей для длительности интервалов между последовательными поступлениями требований на обслуживание

Механизм поступления требований удобнее всего описывать, задавая распределение вероятностей для длительностей интервалов времени между последовательными поступлениями требований на обслуживание. Предположим, что продолжительности интервалов между поступлениями требований статистически независимы, определяются одним и тем же распределением вероятностей и описываются некоторой непрерывной функцией, представляющей собой плотность распределения. Такого рода входной поток требований представляет собой типичный пример так называемого процесса восстановления, а последовательность поступлений является иллюстрацией так называемой последовательности рекуррентных событий. Пусть f(t) есть плотность распределения продолжительностей (t) интервалов между любой парой смежных поступлений (при этом t?0). Определим также величину 1/л как среднее значение длительности временного интервала между поступлениями требований, так что л можно интерпретировать как среднее число поступлений в единицу времени, или как среднюю частоту поступлений. Если функция f(t) задана, значение л выражается через математическое ожидание

(средняя длительность интервала между поступлениями) (1)

Так, например, если единицей времени является 1 ч, а л = 4 есть среднее количество поступлений в течение часа, то 1/л = 0,25 ч, т. е. в среднем в течение каждой четверти часа в систему поступает одно дополнительное требование. Аналогично, если каждые 10 мин в систему поступает в среднем одно требование, то частота поступления л равняется 0,1 требование/мин.

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

f(t)= , t?0 (2)

(экспоненциальное распределение со средним значением 1/л и дисперсией 1/л2),

где е -- основание натурального логарифма (е = 2,71818 . . .).

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

Для проверки того, что экспоненциальное распределение не обладает памятью, допустим, что стартовой точкой является точка

t = 0. Тогда вероятность отсутствия поступлений на интервале (0, Т) равняется вероятности того, что первое поступление имеет место после момента времени Т:

Р[t?T]= = (3)

При этом условная вероятность отсутствия поступлений на интервале (0, Т + К) при условии, что не было ни одного поступления

на интервале (0, Т), по определению равняется

= = = P[t?h] (4)

т.е. зависит только от h. Согласно (4), вероятность отсутствия поступлений на интервале

(T, Т +h) остается одной и той же независимо от того, отсутствуют ли поступления на интервале (0, Т) или в момент времени Т имеет место поступление требования и, следовательно, наблюдается акт возобновления потока.

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

P [Отсутствие поступлений в любом интервале, имеющем длину

h]= = 1 + ++… . (5)

Для достаточно малых положительных значений h член 1 в разложении (5) превосходит по своему значению сумму остальных членов ряда. Следовательно, для достаточно малых значений h вероятность, определяемая соотношением (5), может быть аппроксимирована суммой двух первых членов разложения. Таким образом, для достаточно малых положительных значений h будем иметь

P [Отсутствие поступлений в любом интервале, имеющем длину h] ?1 (6)

Весьма наглядный, хотя и не совсем корректный, способ обоснования правомерности очередного математического хода заключается в принятии следующего допущения: на интервале достаточно малой продолжительности h количество поступлений не превышает единицы [т. е. количество поступлений внутри достаточно малого интервала (Т, T+h) равняется либо нулю, либо единице]. Поскольку приближенная формула для вероятности отсутствия поступлений на интервале

(Т, T+h) имеет вид (6), мы приходим к следующему выражению:

P [Отсутствие поступлений в любом интервале, имеющем длину h] ? (для достаточно малых значений h) (7)

Более последовательный метод вывода формулы (7) связан с разложением в ряд Тейлора точного выражения для вероятности единичного поступления в интервале (Т, Т+h); после этого потребовалось бы показать, что для достаточно малых значений h в упомянутом разложении можно пренебречь всеми членами, исключая (как бесконечно малыми более высокого порядка). В контексте символ ? всюду означает, что в разложении функции в ряд мы пренебрегаем членами «более высокого порядка малости».

Допустим, например, что л равняется четырем поступлениям в час. Тогда вероятность отсутствия поступлений на интервале 0,1 ч, согласно (5), равняется 0,96079, а согласно приближенной формуле (6), 1 -- 0,04 = 0,96; вероятность одного поступления

на указанном интервале, согласно (7), равняется 0,04. Если плотность распределения длительностей интервалов между поступлениями требований на обслуживание имеет экспоненциальный вид (2), то плотность распределения полного времени у для произвольным образом выбранного ряда из п последовательных поступлений определяется следующей формулой:

g(y)= y?0 (гамма-распределение) (8)

где п -- положительное целое число. Величину у можно интерпретировать как сумму п независимых выборок из экспоненциального распределения (2). Тогда

P[Полное время для любой последовательности из n поступлений равно или меньше Т]= =

1- , (9)

в чем легко убедиться, прибегнув к многократному интегрированию по частям.

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

Теперь нам ясно, почему термины «экспоненциальный закон распределения поступлений» и «пуассоновский процесс» являются синонимами. (Иногда используется термин «марковский процесс» или, в сокращенной записи, «М-процесс»)

Легко убедиться, что из (9) и (10) вытекает следующее равенство:

Приведенные выше формулы находят непосредственное применение для описания процессов чистого рождения.

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

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

Мы исходим из следующих постулатов:

(A) Длительности интервалов между последовательными поступлениями взаимонезависимы и распределены идентичным образом; при этом вероятность поступления требования в интервале (Т, Т + К) зависит лишь от h и не зависит от Т. Плотность вероятности, соответствующую такому характеру входного потока, обозначим через f(t).

(Б) Существует некоторая ненулевая вероятность поступления в течение любого интервала h > 0.

(B) При достаточно малых значениях h количество поступающих заявок не превышает единицы.

Предположим для простоты, что система начинает функционировать, начиная с момента 0, причем первое поступление имеет место в момент t (t?0). Отсюда следует, что f(t) представляет собой плотность вероятности как для продолжительности интервалов между двумя поступлениями, так и для фактического времени появления первого требования.

Определим

Пусть t = x есть время первого поступления, причем, согласно постулату (В), в момент х поступает единственное требование. Учитывая постулат (А), мы можем написать

Легко убедиться в том, что функция Рп (Т), определяемая формулой (XI), действительно удовлетворяет уравнению (X); для этого достаточно продифференцировать выражение (XI) по Т. Таким образом, формула (X) нами доказана.

Случай с такси. Приведем пример, иллюстрирующий свойство экспоненциального распределения «не помнить о прошлом» и одновременно демонстрирующий в некотором смысле парадоксальную ситуацию, которая может иметь место в системах массового обслуживания. Представим себе, что мы пытаемся поймать такси в каком-нибудь месте на одной из центральных площадей города. Допустим, что мимо этого места каждые 30 с проходит в среднем одно свободное такси, т. е. средняя продолжительность интервала между появлениями такси в заданной точке равняется 1/л = 30 с.

Предположим, что мы пытаемся поймать такси, начиная с некоторого произвольным образом выбранного момента времени. Сколько в среднем секунд нам придется ждать появления свободного такси? Многие отвечают, что ждать придется 15 с. Так ли это? Ниже будет показано, что такой ответ был бы правильным лишь при условии, что свободные такси появляются у места, где мы их ловим, строго через каждые 30 с. Если имеет место хотя бы некоторый разброс интервалов между появлениями свободных такси у выбранного нами места, продолжительность нашего ожидания всегда будет больше 15 с.

Можно доказать, что если рассматривать систему в произвольный момент времени t, то

Следовательно, если дисперсия в формуле (13) отлична от нуля, то средняя продолжительность ожидания с момента t до появления первого такси, превышает (1/2) -(1/л). Заметим, что в случае экспоненциального распределения длительностей интервалов между последовательными появлениями дисперсия равняется 1/л2 и, следовательно, среднее время ожидания с момента t до появления такси равняется 1/л. Если же дисперсия принимает значения, превышающие 1/л2,то среднее время ожидания свободного такси (отсчитываемое от момента t) оказывается на самом деле большим, чем среднее значение длительности интервала между появлениями свободных такси. Этот результат может показаться на первый взгляд несколько удивительным.

Распределение Эрланга. Другим важным частным случаем распределения длительностей интервалов между последовательными поступлениями требований на обслуживание является распределение Эрланга

где п -- положительное целое число. Для математического ожидания и дисперсии соответственно имеем

Е [t] = 1/л, Var [t] = 1/n л2 (15)

(Это распределение часто обозначают символом Еп.)

Произведя в (14) замену пл -> л, мы получим гамма-распределение (8).

Варьируя надлежащим образом значениями К и п, мы можем использовать распределение Эрланга в качестве хорошего приближения распределений других видов; ряд графиков, иллюстрирующих поведение f(t) при некоторых частных значениях л и п, приведен на рисунке. Следует обратить внимание на то, что при п = 1 распределение Эрланга становится тождественным экспоненциальному распределению. Отметим также, что при п > ?, когда

Var [t] >0, распределение Эрланга соответствует случаю регулярного (или строго периодического) поступления, т. е. случаю, когда длительности (1/л) интервалов между поступлениями одинаковы и не меняются со временем (т. е. являются константами)

3 Распределение вероятностей для длительностей обслуживания

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

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

Так, например, если за единицу измерения времени принимается 1 ч и если м = 5, т. е. в течение 1 ч действующий обслуживающий прибор успевает обслужить пять требований, то среднее время обслуживания одного требования составляет 1/м = 0,2 ч. Аналогично, если на обслуживание одного требования в среднем уходит 30 мин, то скорость обслуживания составляет м = 2 требования в час (при этом в расчет принимается только то время, когда прибор занят обслуживанием). Часто предполагают, что распределение длительностей обслуживания является экспоненциальным:

Основной мотив, побудивший нас принять такое предположение, остается прежним -- он заключается в стремлении упростить математическую сторону вопроса. Однако предположение о том, что механизм обслуживания функционирует в режиме экспоненциального распределения, может одновременно служить некоторым ориентиром при анализе операционных характеристик любой системы массового обслуживания, поскольку в нем находят отражение особенности систем «экстремального» типа, т. е. систем, в которых обслуживающие приборы не обладают памятью. В случае показательного распределения длительностей обслуживания вероятность завершения обслуживания клиента в любой последующий интервал времени (t, t+h) не зависит от того, сколько времени уже потрачено на обслуживание этого требования. Таким образом, если в момент t требование уже обслуживалось и мы рассматриваем систему в момент (t+h), то в силу (4)

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

Рассмотрим очень малый интервал времени (Т, T+h), где h > 0. Тогда, поскольку каждый клиент действует в процессе самообслуживания независимым образом, с помощью приближенной формулы (6) получаем

При этом, учитывая, что h -> 0, мы в процессе обоснования (18) можем ограничиться рассмотрением лишь таких событий, когда на интервале (Т, Т + h) либо ни один из п клиентов не успеваем закончить процедуру самообслуживания, либо заканчивает самообслуживание один из них, т. е. мы пренебрегаем вероятностями того,что в данном интервале самообслуживание заканчивают два или большее число клиентов, считая эти вероятности величинами болем высокого порядка малости.

Другими словами, если в момент T+h в системе находится п клиентов, то предполагается, что можно учитывать лишь а) вероятность того, что в момент Т в ней также было п клиентов и не наблюдалось ни одного случая их выхода из системы, и б) вероятность того, что в момент Т число клиентов внутри системы равнялось п + 1 и наблюдался случай выхода одного клиента из данной системы (при этом должно выполняться условие М > п), т. е.

Перенесем Рп (Т) в левую часть (19), разделим обе части получаемого в результате соотношения на h и устремим h к нулю; после этого будем иметь

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

М -- экспоненциальное распределение продолжительностей интервалов между поступлениями требований или длительностей обслуживания (от определяющего слова «марковский») ;

D -- детерминированное (или регулярное) распределение длительностей интервалов между поступлениями требований или длительностей обслуживания;

Еп -- тг-фазное распределение Эрланга для длительностей интервалов между поступлениями требований или длительностей обслуживания. [Ряд авторов используют также символ Кп, обозначая им гамма-распределение (15).]

GI -- рекуррентный характер входного потока без каких-либо специальных предположений относительно функции распределения;

G -- общий вид распределения длительностей обслуживания (т. е. не делается никаких конкретизирующих предположений относительно функции распределения).

Так, например, для модели с пуассоновским входным потоком, экспоненциальным распределением длительностей обслуживания и единственным обслуживающим прибором символическая запись имеет вид M/M/1. Если бы входной поток был детерминированным, а прочие характеристики модели оставались прежними, символическое представление модели имело бы вид D/M/1; если бы вместо одного обслуживающего прибора только что упомянутая система располагала S приборами, то в обозначениях Кендалла символическое представление модели приняло бы вид D/M/S.

4 Одноканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания

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

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

независимо от того, какого типа модель при этом используется --математическая, имитационная или комбинированная. Часто удается получить приближенное представление об операционных характеристиках сложной системы путем анализа некоторых «экстремальных» или предельных случаев. Один из таких приближенных методов заключается в следующем: система массового обслуживания, насчитывающая п обслуживающих приборов, рассматривается как «механическое» объединение п одноканальных систем, функционирующих независимо одна от другой. Пусть, например, обслуживающая система состоит из пяти приборов, а интенсивность входного потока равняется 20 человек/ч. Тогда приближенно данную систему можно рассматривать как совокупность пяти автономных систем с одним обслуживающим прибором, каждая из которых характеризуется входным потоком с интенсивностью 4 человек/ч.

Этот метод является приближенным по двум причинам: во-первых, предполагается, что требование может попасть на вход любой из упомянутых одноканальных «подсистем» с одинаковой вероятностью (независимо от того, какова длина соответствующей очереди), и, во-вторых, постулируется, что, попав в одну из очередей, требование должно оставаться именно в этой первоначально выбранной очереди. Ожидаемое количество требований, находящихся во всех автономных подсистемах такого рода гипотетической системы, и среднее время пребывания в ней требования, как правило, превышают значения соответствующих операционных характеристик реальных многоканальных систем. Это объясняется тем, что если бы мы применили нашу гипотетическую систему на практике, то обнаружилось бы, что чаще, чем это можно предположить, один из обслуживающих приборов находился бы в незанятом состоянии, в то время как требования простаивали бы в очередях к другим приборам. Если же предположить, что в системе с несколькими обслуживающими приборами очередь является единой и характеризуется дисциплиной «первым пришел -- первым обслуживаешься», то соответствующие аппроксимирующие оценки ожидаемого количества требований в системе и среднего времени, потраченного каждым требованием на ожидание обслуживания, окажутся заниженными по сравнению с фактическими значениями упомянутых показателей.

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

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

Пусть в некоторый момент времени число находящихся в системе требований, включая уже обслуживаемые требования, равняется п. Предположим, что система начинает функционировать с момента t = 0, и определим

Вообще говоря, Рп (Т) зависит от количества требований i, находившихся в системе в момент 0; однако в (2) индекс i нами опущен. Пусть h> 0 есть интервал времени очень малой продолжительности. Если в момент Т +h количество требований в системе равняется , то мы будем считать, что количество требований, которое могло находиться в системе в момент Т, равняется либо п -- 1, либо п, либо п + 1; всеми прочими вероятностями мы пренебрегаем как величинами более высокого порядка малости. Таким образом, при п >> 0 для малых значений h

Первое слагаемое в правой части (3) соответствует возможности одного поступления при отсутствии выходов из системы в случае п -- 1 требований внутри системы в момент Т. Второе и третье слагаемые отражают соответственно возможность отсутствия как поступлений, так и выходов и возможность одного поступления и одного выхода в случае нахождения внутри системы в момент Т п требований. Последний член в правой части соотношения (3) соответствует возможности одного выхода из системы при отсутствии поступлений в случае нахождения внутри системы в момент Т п требований. Как показывает символ да, выражение (3) является приближенным [точное выражение для Рп (Т -- n) содержало бы члены с коэффициентами hk, где k ? 2].

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

в момент 0). Это решение называется неустановившимся, поскольку оно непосредственно зависит от Т . Допустим, однако, что нами рассматриваются значения Рп (Т) при Т >?. Если Рп(Т) стремится при этом к некоторому предельному значению (обозначим его через Рп) и если для данного предельного распределения Е [п] оказывается конечным, то говорят, что система стремится к состоянию (или достигает состояния) статистического равновесия. Назовем предельные значения Рп установившимися или стационарными вероятностями. Прилагательное «стационарный» отражает следующее свойство системы: если количество находящихся в ней требований определяется в произвольно выбранный момент t с помощью распределения Рп, то для любого h > О Рп является также вероятностью обнаружения в системе п требований в момент t + h. Значение Рп можно также интерпретировать как долю времени произвольно большого периода, в течение которой в системе находится п требований.

Если имеет место условие

то стационарные вероятности Рп всегда существуют. Величину с часто называют трафик интенсивностью. Решение, соответствующее равновесному состоянию Рп (Т) = Рп при любом Т, легко найти из условия dPn/dT = 0, отражающего то обстоятельство, что Рп не зависит от Т. Таким образом, для определения Рп требуется лишь приравнять нулю производные, стоящие в левых частях уравнений (4) и (5). В результате будем иметь

Система уравнений в конечных разностях (7) и (8) легко решается методом математической индукции. Начав с рассмотрения (8), получаем

Затем переходим к (7), рассматривая последовательно значения п = 1, 2, 3, . . .; в результате будем иметь

С учетом (6)

Обратите внимание на то, что распределение вероятностей (12) зависит только от траффик-интенсивности р = л/м. Поскольку с ( = 1 -- Р0) также представляет собой ту долю полного времени с начала функционирования системы, в течение которой прибор не простаивает, то эту величину называют иногда коэффициентом использования или коэффициентом загруженности прибора. Существенным является то, что такая интерпретация сохраняет силу даже в том случае, когда не вводится никаких конкретизирующих предположений ни относительно распределения длительностей интервалов между поступлениями, ни относительно распределения длительностей обслуживания (т. е. когда модель относится к типу GI/G/1).

Если через Рп (Т | i) обозначить решение уравнений (4) и (5) при условии, что в начальный момент времени t = 0 в очереди находилось i требований, то можно показать, что

Следовательно, Рп (Т | i) стремится к Рп не медленнее, чем при изменении по экспоненциальному закону. Заметим, что при л>м коэффициент при Т в показателе стремится к нулю . Следовательно, интервал времени Т, в течение которого значение Рп (Т | i) станет почти равным Рп, может быть весьма продолжительным; это свойство «медленного стремления к стационарному режиму» проявляется особенно заметно при больших значениях с и малых значениях i.

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

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

Формулы (16) и (17), вообще говоря, справедливы при любом распределении длительностей обслуживания (т. е. применимы и в случае модели M/G/1)

Рассмотрим теперь плотность распределения для продолжительности пребывания требования в системе обслуживания. Время, в течение которого требование находится в системе, складывается из продолжительности ожидания им обслуживания в очереди и длительности самой процедуры обслуживания. Теперь предположим, что система находится в состоянии статистического равновесия, так что каждое из вновь поступающих требований с вероятностью Рп, определяемой формулой (12), обнаруживает впереди себя п уже ожидающих обслуживания требований. Допустим, что для очереди принята дисциплина «первым пришел -- первым обслуживаешься». Тогда полное время пребывания требования в системе представляет собой сумму п +1 независимых выборок из множества значений, принимаемых случайной переменной, которая характеризуется экспоненциальным распределением, т. е. описывается гамма-распределением с плотностью:

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

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

л--количество требований, поступивших в систему за единицу времени; с-скорость обслуживания (количество требований, обслуживаемых за единицу времени);с= л/м- траффик-интенсивность.

Хотя все перечисленные нами показатели при достаточно больших с < 1 могут принимать сколь угодно большие значения, может пройти весьма много времени, прежде чем система достигнет равновесного состояния. При заданной скорости обслуживания м, когда траффик-интенсивность с незначительна, основная доля среднего времени пребывания требования в системе связана с самой процедурой обслуживания (средняя продолжительность процедуры обслуживания равняется 1/м); однако при возрастании с, т. е. при увеличении интенсивности входного потока л, большая часть времени пребывания требования в системе (в смысле его среднего значения) обусловлена ожидание м обслуживания в очереди. Обратимся к таблице. Пусть единицей времени является 1 ч (или 60 мин). Рассмотрим случай, когда с = 0,8. При этом прибор простаивает в среднем в течение 0,2 ч (т. е. каждые 12 из 60 мин), а среднее количество требований, находящихся в системе, равняется 4. При м= 10, т. е. когда скорость обслуживания равняется 10 человек/ч (на каждое требование прибор расходует в среднем 6 мин своего рабочего времени), средняя продолжительность пребывания требования в системе равняется 0,5 ч (30 мин), а средняя продолжительность его пребывания непосредственно в очереди -- 0,4 ч (или 24 мин). Если с = 0,8, но при этом значения как интенсивности входного потока, так и скорости обслуживания удваиваются (т. е. м= 20), средняя продолжительность пребывания требования в системе и средняя продолжительность его ожидания начала обслуживания уменьшаются в два раза.

Случай произвольного распределения длительностей обслуживания.

Весьма несложным оказывается вычисление ожидаемого количества требований в системе массового обслуживания и средней продолжительности их пребывания в ней в том случае, когда входной поток требований характеризуется экспоненциальным распределением, а относительно вида распределения длительностей обслуживания не делается никаких специальных предположений (т. е. в случае, когда модель относится к типу M/G/1).

Пусть

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

Соотношения (29) и (32) часто называют формулами Поллачека -- Хинчина.

Нетрудно проверить, что если плотность распределения g (f) является экспоненциальной и, следовательно, V = 1/м2, то формулы (29), (30) и (32) преобразуются соответственно в формулы (13), (15) и (20). Эти формулы определяют также соответствующие математические ожидания в случае, когда скорость обслуживания постоянна, так как при этом V = 0. Другими словами, при

V = 0 полученные выше формулы описывают модель типа M/D/I, Обратите внимание на то, что средние значения всех указанных выше показателей являются линейными функциями V и зависят лишь от частоты поступления требований л, траффик-интенсивности р и дисперсии

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

Заметим далее, что в условиях статистического равновесия

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

Дисциплина очереди при наличии приоритета.

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

он обнаружит на своем рабочем столе ряд телефонограмм, среди которых может оказаться и телефонограмма от какого-нибудь важного должностного лица, в подчинении которого данный молодой административный работник находится. Скорее всего, что в первую очередь он уделит внимание именно этой телефонограмме. Предположим, что требования, поступающие на вход системы обслуживания, можно подразделять на г различных категорий, каждой из которых приписывается приоритет k (k = 1, 2, . . ., г), выраженный соответствующим номером. Допустим, что приоритет падает с увеличением его номера, т. е. приоритет 1 оказывается наивысшим, а приоритет г -- самым низким. Как только прибор заканчивает обслуживание того или иного требования, он немедленно переходит к обслуживанию следующего требования, отдавая при этом предпочтение тому из находящихся в очереди требований, приоритет которого оказывается наиболее высоким. (Если в очереди находится несколько требований с одинаковыми приоритетами, очередность их обслуживания определяется правилом ?первым пришел -- первым обслуживаешься?.) В некоторых случаях, кроме того, предполагается, что при поступлении в систему обслуживания требования с более высоким приоритетом по сравнению с приоритетом требования, которое в этот момент находится в процессе обслуживания, система бросает уже начатую процедуру обслуживания и переключается на обслуживание требования с более высоким приоритетом. Другими словами, предполагается использование дисциплины нокаутирующих приоритетов. Приведенные ниже результаты относятся к случаю ненокаутирующих приоритетов. Допустим, что поток требований, обладающих приоритетом k, является пуассоновским при значении k = 1, 2, . . ., r, причем соответствующие средние частоты поступлений равняются лk.

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

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

Рассмотрим систему в момент времени, следующий непосредственно за завершением очередной процедуры обслуживания. Тогда для вновь поступившего требования с приоритетом k среднее время ожидания в очереди определяется формулой

Нетрудно убедиться в том, что при r = 1 выражение (35) сводится к (32). Поскольку лk / есть вероятность того, что вновь поступившее требование обладает приоритетом k, среднее время пребывания в очереди произвольным образом выбранного требования вычисляется по следующей формуле:

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

В некоторых задачах продолжительность процедуры обслуживания зависит от номера (или, как говорят, от уровня) приоритета. Тогда, обеспечивая требованиям с более высокими уровнями приоритета ускоренное обслуживание, мы тем самым сокращаем среднее время ожидания в очереди, вычисленное по суммарному выходному потоку обслуженных требований. В качестве иллюстрации этого утверждения вновь обратимся к случаю, когда л= 18, м= 20 (так что коэффициент загруженности обслуживающей системы при этом равняется 0,9, а среднее время ожидания в очереди 0,45). Перейдем теперь к схеме обслуживания с двумя уровнями приоритета и предположим, что л1= л2= 9, a м1= 30 и м2= 15, так что коэффициент загруженности ? r= 9/30+9/15 = 0,9 (т. е. остается таким же, как и в схеме обслуживания при отсутствии приоритетов). С помощью (35) и (36) легко убедиться, что в этом случае средняя продолжительность пребывания в очереди требования с приоритетом 1 равняется 1/14 = 0,0714, а требования с приоритетом 2 -- 10/14 = = 0,7142, т. е. меньше, чем в случае, когда м1= м2= м3 = 20. При этом средняя продолжительность пребывания в очереди, вычисленная на суммарном ансамбле обслуженных требований, равняется 0,3928, т. е. оказывается меньшей по сравнению с аналогичной операционной характеристикой системы без приоритетов, а также по сравнению со случаем, когда м1= м2 =20.

5 Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания

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

причем длительности обслуживания взаимонезависимы как для отдельно взятого прибора, так и по системе в целом. Уравнения в конечных разностях, аналогичные приведенным в предыдущем разделе уравнениям (7) и (8) для случая одноканалъной системы массового обслуживания и определяющие значения Рп в условиях установившегося режима, имеют следующий вид:

Решение системы уравнений (3) имеет вид

Установившийся режим функционирования системы массового обслуживания, характеризующийся соотношениями (4) и (5), возможен при условии л< мS (или < S.

В случае неограниченного количества обслуживающих приборов (например, в условиях самообслуживания) первая из формул (4) становится применимой для любого значения п. Следовательно, в этом случае Рп принимает пуассоновский вид, причем Е [п] = р.

Для такой модели используют символическое обозначение М/М/?. При S = ? пуассоновский характер Рп имеет место фактически при любом виде распределения длительностей обслуживания, т. е. и в случае M/G/?.

Формулы (4) применимы и в том случае, когда действует ограничение на суммарное количество требований М (?S), которое может находиться в системе. При этом п ? М, а Р0 определяется из условия

Отметим, кроме того, что формулы (4) остаются при этом справедливыми и в случае, когда л< мS

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

Некоторые авторы называют величину, определяемую формулой (6), вероятностью задержки; на наш взгляд, более удачным является термин виртуальная задержка. Величина определяет долю времени, в течение которого требования фактически пребывают в системе.

Введем в рассмотрение следующие величины:

В правой части (13) первое слагаемое представляет собой Е [Продолжительность ожидания в очереди], а второе -- Е [Продолжительность процедуры обслуживания].

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

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

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

6 Процессы рождения и гибели

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

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

Будем считать, что исследуемая система функционирует непрерывно, т. е. не имеет определенной стартовой точки, и в момент t характеризуется количеством находящихся в ней требований, которое мы обозначим через п (п = 0, 1, 2, . . .). Нам, разумеется, нужно договориться относительно выбора на оси времени начала отсчета t. Пусть в качестве начала отсчета времени выбрана точка t = 0; обозначим одновременно через i количество требований, находящихся в системе в момент 0. Пусть, по определению,

Поскольку процесс однороден во времени, величина Pin (h) при h > 0 определяет не только вероятность перехода на интервале (0, h), но и вероятность перехода на интервале (Т, Т+h) при произвольном значении Т, т. е. представляет собой вероятность того,что в момент Т+ h в системе будет находиться п требований при условии, что в момент Т в данной системе находилось i требований. Нами постулируется, что вероятности Pin (Т) удовлетворяют известным уравнениям Колмогорова -- Чэпмена для однородныхво времени марковских процессов.

Эти уравнения имеют следующий вид:

при любых значениях i и т. Соотношения (2) эквивалентны утверждению, что вероятность обнаружения в системе п требований в момент Т + h при условии, что в системе было i требований в момент Т, можно определить путем сложения произведений совместных вероятностей наличия в системе т требований в момент Т при наличии в ней i требований в момент 0 и вероятностей наличия в системе п требований в момент T+h, при условии, что в момент Т в системе находилось т требований. Так называемое марковское свойство процесса просто означает, что действительно существенной информацией для описания состояния системы в момент Т является лишь информация о количестве требований, находящихся в системе в этот момент (это число мы обозначили через т), а информация о всей предыстории протекания процесса до момента Т оказывается совершенно несущественной . В этом смысле система ?не обладает памятью? (или, как иногда говорят, является системой ?без последействия?) и, следовательно, условие (2) является нетривиальным.

Процесс рождения и гибели является частным случаем дискретного марковского процесса, определяемого уравнением (2). Предположим, что в течение очень малого интервала времени (Т, Т+h), причем h > 0, количество поступивших в систему требований, так же как и количество требований, обслуженных системой, не превышает единицы (т. е. равняется либо нулю, либо единице). Для этого случая мы получим

Соотношение (6) является уже не приближенным, а точным, так как при h > 0 члены, опущенные нами в (5), в процессе указанного предельного перехода обращаются в нуль. Уравнение (6) позволяет также описать случай, когда п = 0; для этого достаточно положить

л-1= 0 и м0 = 0. Итак, (6) представляет собой систему уравнений для п =0О, 1, 2, . . . при начальном количестве требований в системе, равном i.

Термин опережающие уравнения отражает то обстоятельство, что при их выводе рассматривалось положительное приращение времени в пределах интервала (Т, T+h), где h > 0, а в качестве приближенных формул для вероятностей переходов были использованы соотношения (3) и (4). Можно вывести также ?запаздывающие уравнения?, рассматривая переходы на интервале (Т+ h, Т) при h > 0 [или, что то же самое, на интервале (Т, T+h) при h < 0] и используя аналоги соотношений (3) и (4) для Pim (h), построенные применительно к данному случаю. В получаемых таким путем дифференциальных уравнениях значение п в момент Т считается заданным, a i (т. е. количество требований, находящихся в системе в момент 0) варьируется, принимая значения i = 0, 1, 2, ....

Систематизация полученных ранее результатов. Попытаемся теперь показать, что из уравнений (6) вытекают (как частные случаи) уравнения для ряда моделей, анализ которых проведен нами в предыдущих разделах данной главы. Рассмотрим модель чистого рождения с пуассоновским входным потоком . Для чистого рождения лn = л,, а мn = 0 при любых значениях п. В предположении, что в момент 0 i = 0, уравнение (6) переходит в уравнение

что согласуется с приведенными до этого формулами (10) и (XI) для i = 0.

Примеры.

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

Пример 1. Предположим, что поток требований является пуассоновским с параметром л, причем будем считать, что каждое требование обслуживает себя в соответствии с экспоненциальным распределением длительностей обслуживания с параметром м. (Такую систему можно квалифицировать как систему с бесконечно большим количеством обслуживающих приборов и представить символически в виде М/М/?. Таким образом, лn = л,, а мn = мn.

Следовательно,

Пример 2. Пусть имеется один прибор, характеризующийся экспоненциальным распределением длительностей обслуживания, т. е. мn = м (п ?1). Однако допустим, что наблюдаются отказы требований присоединиться к очереди, причем наблюдается следующая закономерность: лn = л/(n+1). Нетрудно убедиться, что при сформулированных выше предположениях мы также придем к формулам (17) и (18).

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

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

Пусть в момент t число вышедших из строя агрегатов равняется п и, следовательно, число действующих агрегатов равняется М -- п. Тогда вероятность того, что в течение очень малого интервала [t, t + h] (h > 0) произойдет поломка одного из агрегатов, которые в момент t нормально функционировали, определяется следующей приближенной:

Простых формул для ожидаемого количества вышедших из строя агрегатов, к сожалению, не существует. Однако в каждом конкретном случае значение Е [га] легко вычисляется, если воспользоваться уже известными численными значениями Рп, найденными с помощью формулы (25).

Вопросы интерпретации модели.

Вероятностная структура каждой из рассмотренных выше моделей массового обслуживания описывалась нами с помощью распределения продолжительностей интервалов между поступлениями требований и распределения длительностей процедур обслуживания. Пока речь шла о системах с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания, никаких неясностей в интерпретации соответствующей модели не возникало. Однако в тех случаях, когда Лn является некоторой функцией n , подобрать компактное аналитическое представление соответствующей функции распределения оказывается далеко не простым делом, а в ряде случаев просто невозможным. Это объясняется сложным характером зависимости числа поступающих требований от состояния системы и режима ее функционирования. Аналогичные трудности возникают и в тех ситуациях, когда от состояния системы зависит мn. Таким образом, легко интерпретируется лишь процесс рождения и гибели частного характера, а именно процесс с пуассоновским входным потоком и показательным распределением длительностей процедур обслуживания. Следует отметить, что подобного рода трудности возникают и в связи с определением распределений вероятностей и вычислением математических ожиданий продолжительностей пребывания требований в обслуживающей системе (даже в тех случаях, когда имеет место дисциплина очереди ?первым пришел -- первым обслуживаешься?).

7 О других методах массового обслуживания

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

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

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

Литература

1. Г.Вагнер «Основы исследования операций», Том 3, Глава 20

2. Таха, Хемди А «Введение в исследование операций», 7-ое издание