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

Факультет информационных технологий Кафедра высшей математики и кибернетики Дисциплина «Модели и методы управления».

СРС.

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

Выполнила: Ахметова Д, ФИТ (АиУ), 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,71 818.. .).

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

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

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,96 079, а согласно приближенной формуле (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/л). Заметим, что в случае экспоненциального распределения длительностей интервалов между последовательными появлениями дисперсия равняется 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), средняя продолжительность пребывания требования в системе и средняя продолжительность его ожидания начала обслуживания уменьшаются в два раза.