Классификация систем массового обслуживания и их основные элементы

Содержание

Введение..................................................................................................

1. Классификация СМО и их основные элементы ...............................

2. Обслуживание с ожиданием..............................................................

3. Пример использования СМО с ожиданием......................................

Расчеты...................................................................................................

Выводы...................................................................................................

Список литературы................................................................................

Приложение 1.........................................................................................

Приложение 2.........................................................................................

ВВЕДЕНИЕ

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

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

Средства, обслуживающие требования, называютсяобслуживающими устройствами

иликаналами обслужи
вания
.

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

Совокупность однотипных обслуживающих устройств называетсяîáñëóæèâàþù
èìè óñòðîé
ñòвами.
Такими системами могут быть телефонные стан­ции, аэродромы, билетные кассы, ремонтные мастерские, склады и баз
ы снабженческо-сбытовых организаций и т.д.

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

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

Раздел І.
Классификация СМО и их

основные элементы

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

По состав
у СМО бываютодноканальные

(с одним обслуживающим уст
­ройством) имногоканальными

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

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

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

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

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

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

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

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

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

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

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

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

1)
Свойством стационарности,

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

2)
Отсутствия последействия,

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

3)
Свойством ординарности,

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

При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:

вероятность того, что в обслуживающую систему за время t поступит именноk
требований:

где. -
среднее число требований, поступивших на обслуживание в единицу времени.

На практике условия простейшего потока не всегда строго выполняются. Часто имеет место нестационарность процесса (в различные часы дня и различные дни месяца поток требований может меняться, он может быть интенсивнее утром или в последние дни месяца). Существует также наличие последействия, когда количество требований на отпуск товаров в конце месяца зависит от их удовлетворения в начале месяца. Наблюдается и явление неоднородности, когда несколько клиентов одновременно пребывают на склад за материалами. Однако в целом пуассоновский закон распределения с достаточно высоким приближением отра­жает многие процессы массового обслуживания. Почему такое предположение в ряде важных случаев оказывается верным, дает ответ общая теорема А.Я.Хинчина, которая представляет исключительную теоретиче­скую и практическую ценность. Эта теорема имеет место в случае, когда входящий поток можно представить в виде суммы большого числа незави­симых потоков, ни один из которых не является сравнимым по интенсив­ности со всем суммарным потоком. Приведем “не строгую” формулировку этой теоремы (полная формулировка и доказательство приведены в).

Теорема (А.Я.Хинчин)

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

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

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

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

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

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

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

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

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

гдеv
- интенсивность обслуживания одного требования одним об­служивающим устройством, которая определяется из соотношения:

, (1)

где-
среднее время обслуживания одного требования одним об­служивающим устройством.

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

где n - количество обслуживающих устройств.

Важным параметром СМО является коэффициент загрузки ,

который определяется как отношение интенсивности поступления требований к интенсивности обслуживания v.

(2)

гдеa
-
коэффициент загрузки; -
интенсивность поступления тре­бований в систему; v
-
интенсивность обслуживания одного требования одним обслуживающим устройством.

Из (1) и (2) получаем, что

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

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

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

.

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

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

Раздел
ІІ.
Обслуживание с ожиданием

1.
Постановка задачи.

СМО с ожиданием распространены наиболее широко. Их можно разбить на 2 большие группы - разомкнутые

и замкнутые

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

К замкнутым

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

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

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

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

Мы рассмотрим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена К.Эрлангом. на n одинаковых приборов поступает простейший поток требований интенсивности . Если в момент поступления имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь прибывшее требование становится в очередь за всеми теми требованиями, которые поступили раньше и ещё не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживанию очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент времени не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x). Предполагается, что при x0.

где - постоянная.

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

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

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

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

Требуемое доказано.

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

,
плотность расп
ределения ко­торого дается формулой

где >
0, a k
— целое
положительное
число.

Распределение Эрла
нга представляе
т собой распределение
суммы k
- не
зависи
мых сла
гае
мых, каждое
из
которых и
меет рас­пределение
(1).

Обозначим для случая распределения (1) через время обслуживания требования. Тогда средняя длительность обслуживания равна

Это равенство даст нам c
посоá оценки
п
араметрап
о оп
ытным
дан
ным. Как ле
гко вычислить,
ди
сп
ерсия длительности
обслуживания
равна

2.
Процесс обслуж
ивания как марковск
ий случайны
й процесс.

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

В каждый момент рассматривае
мая систе
ма может находи
ть­ся в одном и
з следующих состоян
ии
: в моментt
в системе на­ходятсяk
требован
ии
(k=
0,
1, 2, ...).
Еслиkrn,
то в систе­ме на
ход
ятся и обслуживаются
kтребований
, а m-k
-приборов
свободны. Если km, то m требований обслуживаются, а k-m находятся в оче
ред
и и ожидаю
т обслуживания.
Обозначим
че
рез состояние, ког
да в си
сте
ме находятсяk
треб
овани
й. Таким
образом, система может находиться в состояниях
..
. Обозначи
м через —
вероятность
того, что система в мо­мент t
окажется в состояни
и .

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

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

моментами поя
вления н
овых требований;

длительностью обслуживания требован
ий, поступивши
х после
.

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