1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 34
Текст из файла (страница 34)
Ы. Шуренкова [Ц. 1е В. В. Гзедевзе, Н, Н. Коваленко ГЛАВА 4 ПОЛУМАРКОВСКИЕ МОДЕЛИ СИСТЕМ ОБСЛУЖИВАНИЯ 4 4.1. Классификация систем массового обслуживания Системы массового обслуживания можно классифицировать по логической структуре процесса обслуживания (чпсло приборов, порядок приоритетов; возможность ожидания я т. п.), а также по аналитическим предпосылкам относительно входящего потока требований и распределения времени оослуживания. Общепринятой является классификация классических систем массового обслужпваппя, предложенная Д. Кендаллом.
Многими авторами зта классификация расширялась (укалтем, например, книгу А. А. Боровкова 111) . Нам будет достаточно классификации Кендалла. Система массового обслуживания кодируется набором символов А!В!т либо А!В!т(г, что означает следующее: А — символ входящего потока,  — символ распределения времени обслуживания, ш — символ числа приборов, г — символ числа мест для ожидания требований. Переменные А, В могут принимать следующие значения: А=6,61,Е„Р,М; В=6,Е„Р,М.
Если А 6(депега1), то входящий поток — более общий, чем поток восставовления, 61 (депега1 1пдерепдеп1) — поток восстановления. Если А = Е„имеем поток Эрлакга й-го порядка, т. е. поток, образованный каждым й-м требованием простейшего потока, Р— регуляриый поток, Лу — простейший поток (от слова Магкот1ап). Относительно времени обслуживания предполагается, что зо всех случаях длительности обслуживания различных требований независимы в совокупности, одинаково распределены и ие зависят от входящего потока. В = 6 означает, что распределение времени обслуживания— общего вида; Е,.
Р, М имеют тот же смысл, что и в случае входящего потока. Так, ЛХ означает, что обслуживание производится по показательному закону. Символ т обозначает число обслуживающих приборов. Если ка его месте стоит латинская буква (т, с и т. п.), вто означает, что число приборов может быть произвольным; иногда указывается конкретное значение числа приборов (1, 2 и т.
д.). То нее откосится и к символу г. Системы с ожиданием А!В!т! ~ коди- 179 5 4»ь системА Зцсю руются более просто: А~В~И». Системы с потерямп можно теперь кодировать так: А)В~И»~0. Обычно предполагается, что в системе Л!В~в»)г имеется обп«ая очередь; требования обслуживаются в порядке очереди. Если система характеризуется какими-либо особенностями, последние дополняются к введенным символам в качестве словесного описания. Например, говорят: «система М~С!2 с инверсным порядьои обслуживания», «система 066~1 с ненадежным обслуживающим прибором». Словесное описание отменяет соответствующие обычные предположения, подразумеваемые в предшествующих символах. б гь2. Система М)б(1 '1.
Постановка задачи и обозначения. Теория, развернутая в 1 1.5, исходит из весьма ограничительного предположения: поток требований является простейшим, длительность обслуживанкя имеет показательное распределение. Ъже Эрланг делал попытки отказаться от второго условия и рассмотрел случаи, когда обслуживание требует времени, которое подчинено равномерному в некотором отрезке (а, Ь), нли же эрланговскому распределению при некотором целом к. Давно было ясно, что не только для развития теории, но и для целей практики исключительно важно рассмотреть задачу обслуживания с ожиданием в общих предположениях как относительно потока требований, так и относительно распределения длительности обслуживания.
Долгое время существовало мнение, что поток с очень хорошим приближением можно считать простейшим, по крайней мере в задачах телефонии, и что особенно существенно научиться пзучать проблемы возникновения и обслуживания очереди, когда длительность обслуживания имеет произвольное распределение. Как мы уже говорили, для системы обслуживания с ожиданием (с очередью) особый интерес представляет изучение распределения длительности ожидания начала обслуживания, В этом вопросе, которому посвящено большое число работ, получено весьма существенное продвижение, особенно в том случае, когда имеется один обслуживающий прибор.
Мы ограничимся этим случаем и изучим вопрос о разыскании распределения времени ожидания начала обслуживания в следующих условиях: 1) требования обслуживаются в порядке очередностп появления; 2) поток требований простейший; его интенсивность равна Х; 3) распределение длительности обслуживания произвольно; в дальнейшем мы будем обозначать его через В(х): В(я) = Р(т)~х), В(я) =1 — В(х), где ц — длительность обслуживания, М») =т( со; 42» 130 гл.
4, полгмхвковскив молили снствм овслгзкивьния уз (з ~о ~т уз ~з у, ~о (2) При о~1 М (т„+, ) т„= 1) = М А„— 1 = ).т — 1; М (т„+т ~ у = О) = МА = Хт. 4) имеется один обслуживающий прибор, который не портится н способен немедленно после окончания обслуживания одного требования приступить к обслужнванию следующего. Первое рептенне задачи в зтпх условиях было найдено А. Я. Хинчиным [4) в 1932 г., а затем им же несколько изменено в неоднократно цнтированноп лами монографии [21. В более широких предположениях зта задача позднее изучалась ннымн приемами Лпндли [Ц, В. Смитом [Ц, Поллачеком [21, Такачем [Ц и др.
2. Вложенная цепь Маркова. Обозначим через ~ моменты окончания обслуживания и-го требования (и = 1, 2, 3, ...), через т(1) — число требований в системе в момент й Пусть т„= т(~„+ + О), т. е. т — число требований, оставшихся в системе после ухода из пее и-го по счету требования. Легко видеть, что последовательность (т„, и ~ 1) образует цепь Маркова.
Данная цепь Маркова непрнводпма. Действительно, из любого состояния з мояоно с положительной вероятностью попасть в состояние 0: достаточно, чтобы в течение 1 последовательных длительностей обслуживания новые требования не поступали. Эта цепь также является непериодической, поскольку из состояния 0 можно возвратиться в то же состояние за один шаг (условием для этого является непоступление требований за время обслуживания одного требования) .
Проверим условия зргодической теоремы из $ 3.1, п. 2. Если м„, ~ 1, то т„= т, + А — 1, где А — число требований, поступивших в систему за время т~ обслуживания п-го требования. Если же т,-з = О, то т, = А . Найдем распределение случайной величины А„. При условии, что ц„= х, вероятность поступления й требований составляет е з"().х)"/й!; усреднение по распределению случайной величины приводит к следующему равенству: Р(А„= й) = —,~е ~з()х) о(В(х) = [зз Ус' в0.
(1) о Отсюда МА„= ~ ЙЬ, = )т. Матрица перехода (т ) имеет вид з=о 181 З А.г. СИСТЕМА М~О)1 Введем параметр Р = Хт, называемый загрузкой однолинейной системы массового обслуживания и играющий важнейшую роль з псследовании поведения очередей (см, 4 1,2), Пусть р ( 1. Тогда, ооозначив е = 1 — р ) О, найдем М(т +2~ т =1) =1 — е, 2)1; М(т„+,! т„= О)( оо. Такам образом, условия теоремы з 3.1, и.
2, выполняются при 1(т) = т, Следовательно, цепь Маркова (т„) обладает эргодическли распределением ль = 1пп Р(т„= й) (й = О, 1, 2...). (3) Как известно из теории цепей Маркова, (ч,) определяются системой уравнений ло = ~ЧЗ„л,Р;А (й = О, 1, 2, ...), (4) О.--О где ри — элементы матрицы Р, с дополнительным условием Х ч„=1. (5) А=-о В салу (2) уравнения (4) имеют следующий вид: ль = 2', л„,„Д0+ ~,~„й)О. (6) 1(г) = ~ч~ д,г, л(г) А=о предполагая, что ~Ы ( 1, и ор (з) = ) е ' ЫВ (з), о Вез) О.
Умножим обе части формулы (6) на г" и просуммируем по всем й: А г ~ лз о+А + л,~(г) 0=0 Ю - Х 1;го .'Е ." 'л.—;+, + лд (г) = О=о А=О = г 1(г) (л (г) — (1 — х) ло); л (г) = ~~ А=О Систему (5) — (6) удобно исследовать методом производящих функции. Введем следующие обозначения: 189 гл 4, полумАРкОВскив модели систем ОБслужиВАния отсюда п(г)= п,(1 — г)/(г)/(/(г) — г). (7) При г - 1 /(г) — г - (1 в г)(1 — /'(1)), так что 1 = я(1) = яо/(1 — /'(1)), откуда я, = 1 — /'(1) и я (г) = (1 — /'(1))(1 — г)/(г)/(/(г) — г). Поскольку /(г) = Д /ог", имеем о=о ~Ю Ю /(г) = ~'„— ~е ~(Ххг)" с)В(х) = ~е „~ —,(Ххг)" дВ(х) = о о = ~ е и )ЫВ (х) =. ф(Х (1 — г)).
(8) о Перестановка суммы и интеграла законна, поскольку ~ е ~~ — „, (Ххг) ИВ(х)(~ЫВ(х) — ~ 0 А А и при достаточно больших и ) — ().тг) е г'ОВ(х)( — ()Аг)" е ~ . +г о Продифференцировав выражение (8), получим 1'(г) = — ) ~'(),(1 †.) ), откуда 1 — /'(1) 1 — Ат = 1 — р, и, окончательно, (1 — р) () — о) ~Р (А И вЂ” г)) "(') — р(х( —.)) —. (9) Изученная величина у„ — число требований, остающихся в системе после окончания обслуживания и-го требования. Пусть теперь у„— число требований, заставаемых в системе и-м требоваинеи. Таким образом, если 1 — момент поступления и-го требования, то у„= у(г„— 0). Изучим предельное распределение случапных величин уо.
Эти величины не образуют цепи Маркова. Для построения цепи Маркова расширим. фазовое пространство. $4 2. систимл м~ о О 183 Пусть 1 = 1(и) — наибольшее значение 1 ( и, для которого ,,', = О, 1' = Г(и) = и — 1(и). Тогда рассмотрим случайную последовательность г Р~ ~ к+м тл+зт Эта последовательность является однородной цепью Маркова.
1 Если чз = Й, то при отсутствии входящих требований на протяжении й интервалов обслуживания будет т„+„=(О; 0). Такам образом, (т ) — неприводимая цепь Маркова. Она также неперподична, поскольку можно возвратиться в нулевое состояние за один шаг. При и ~ 2 равенство т =(О; О) выполняется всякий раз, когда т —, = О. Отсюда Р (ч„= (О; 0)) — ~ 1(ш Р (т„, ~ = О) = л = 1 — р > О. Следовательно, цепь Маркова (т ) обладает зргодическим распределением. Обозначим через л' (й - й + 1) число тех 1, 1 < 1 < и, для которых т~ = Й, через Ж (Й + 1 -~- Й) — число тех 1, 1 ~ 1 < и, для которых т~ = й. Обозначение оправдано тем, что при т; =й в момент ~; функция т(1) переходит из состояния й в состояние й+ 1, а при т; = Й в момент 1; происходит обратный переход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
