1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987).djvu), страница 6
Описание файла
DJVU-файл из архива "1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987).djvu", который расположен в категории "". Всё это находится в предмете "теория массового обслуживания (асвк)" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 6 - страница
Далее ясно, что )',(а)=е "' и ),(а+1)=е "'+". А так как всегда (,(а+Г)= =)с(а)(,(г), то е "'"+" = е '"У,(Е) и, следовательно, (. (Г) = е-" - Ь(~). Требуемое доказано. Несомненно, что в реальной обстановке показательное время обслуживания является, как правило, лишь грубым приближением к действительности. Так, нередко время обслуживания не может быть меньше, чем некоторая определенная величина. Предположение хсе (т) приводит к тому, что значительная доля требований нуждается лишь в кратковременной операции, близкой к О.
Позднее перед нами возникает задача освобождения от излишнего ограничении, накладываемого пречположением (1). Необходимость этого была ясна уже самому Эрлангу, и он в ряде работ делал усилия найти иные удачные распределения для длительности обслуживания. В частности, нм было предложено так называемое распределение Эрланга, плотность распределения которого дается формулой О при 8~(О, )с )) ета при й)О (у — 1)! где (с ) О, а Й вЂ” целое положительное число. Распределение Эрланга представляет собой распределение суммы Й независимых слагаемггх, каждое из. которых имеет распределение (1). 6 Ьз.
ОВСЛУЖИВАНИЕ С ОЖИДАНИЕМ 27 Обозначим для случая распределения (2) через 2) время обслуживания требования. Тогда средняя длительность обслуживания равна Мц = ~ х АР (х) р~ хе-з"Йх = —. 1 р' Это равенство дает нам способ оценки параметра 12 по опытным данным.
Как легко вычислить, дисперсия длительности обслуживания равна Рч = Мч' — (Мц)' = —,. 1 Р' 2. Процесс обслуживания как марковский случайный процесс. В указанных нами предположениях о потоке требований и о длительности обслуживания задачи теории массового обслуживания приобретают некоторые черты, облегчающие проведение исследований. Мы отмечали уже вычислительную простоту.
Теперь отметим более принципиальное сообрансение, которое станем развивать применительно к изучаемой задаче. В каждый момент рассматриваемая система может находиться в одном из следующих состояний: в момент 8 в системе находятся й требований (к= О; 1, 2, ...).
Если й(т, то в системе находятся и обслуживаются й требований, а лг — й приборов свободны. Если й) т, то т требований обслуживаются, а й — т находятся в очереди и ожидают обслуживания. Обозначим через Е, состояние, когда в системе находятся й требований. Таким образом, система может находиться в состояниях Е„Е„Е,, ...
Обозначим через Р,(1) — вероятность того, что система в момент 1 окажется в состоянии Е.. Сформулируем, в чем заключается особенность изучаемых нами задач в сделанных предположениях. Пусть в некоторый момент 80 наша система находилась в состоянии Еь Докажем, что последующее течение процесса обслуживания не зависит в смысле теории вероятностей от того, что происходило до момента 1,. Действительно, дальнейшее течение обслуживания полностью определяется тремя следующими факторами: моментами окончания обслуживаний, производящихся в момент 1,; моментами появления новых требований; длительностью обслуживания требований, поступивших после аь В силу особенностей показательного распределения длительность остающейся части обслуживания не зависит от того, как долго уже продолжалось обслуживание до момента 1,.
Так как поток требований простейший, то прошлое не влияет на то, как много требований появится после момента г,. Наконец, длнтель- 28 ГЛ. 1 ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ ность обслуживания требований, появившихся после Ф„никак не зависит от того, что и как обслуживалось до момента Известно, что случайные процессы, для которых будущее развитие зависит только от достигнутого в данный момент состояния и не зависит от того, как происходило развитие в прошлом, называются процессами Маркова или же процессами без после- действия.
Мы доказали сейчас, что система с ожиданием в случае простейшего потока и показательного времени обслуживания представляет собой случайный процесс Маркова. Зто облегчает дальнейшие рассуждения. 3. Составление уравнений. Задача теперь состоит в том, чтобы найти те уравнения, которым удовлетворяют вероятности Рг(!). Одно из уравнений очевидно, а именно для каждого ;э Р,(!) =1. (й) о=о Найдем сначала вероятность того, что в момент Г + й все приборы свободны. Это может произойти следующими способамп: в момент ! все приборы были свободны и за время й новых требований не поступало; в момент 1 один прибор был занят обслуживанием требования, все остальные приборы свободны; за время й обслуживание требования было завершено и новых требований не поступило. Остальные воэмоя!ности, как-то: были заняты два или три прибора и эа время й работа на них была закончена — имеют вероятность о(й), как легко в этом убедиться.
Вероятность первого из указанных событий равна Р,(!)е '" = Ро(!) (1 — Ух+о()г)), вероятность второго события Рг(!) е "'(1 — е гл) = Р,(!) гг)г+ о(й). Таким обрааом, Ро (г+ й) = Ро (!) (1 — Хй) + р йр, (! ) + о ()г), Отсюда очевидным образом приходим к уравнению Ро(г) = — ЛРО(г) + )гР1(!). Перейдем теперь к составлению уравнений для Рг(г) прп й>1. Рассмотрим отдельно два различных случая; 1 о= й(гп и й ~ и, Пусть вначале 1 ~ й ( пг. Перечислим только существенные состояния, из которых можно прийти в состояние Е, в момент 1+ й.
Эти состояния таковы: В момент г система находилась в состоянии К„за время й новых требований не поступило и ни один прибор не окончил % Ьз. ОБСЛУЖИВАНИЯ С ОЖИДАНИКМ 29 обслуживания. Вероятность этого события равна Р,(!) е-'"(е-™) ! = Р„(!) (1 — ЛЬ вЂ” Ь1!Ь+ о (Ь) ). В момент г система находилась в состоянии Е„„эа время Ь поступило новое требование, но ни одно ранее находившееся требование не было закончено обслуживанием. Вероятность этого события равна Р,, (Г) (1 — е™) (е !А)'-' = ЛЬР!, (2)+ о(Ь), В момент г система находилась в состоянии Еы о аа время Ь новых требований не поступило, но одно требование было обслуя!ено.
Вероятность этого равна Рь+! (!) е ~Сьь.!! (е "ь)" (1 — е э ) = Рьь! (2) (Ь + 1) (АЬ + о (Ь). Подобные же рассузкдения для Ь > эз приводят к уравнению Р, (Г) = — (Л+ т1!) Рь(!) + ЛРь ! (!) + лэрР„+! (Г). (5) Для определения вероятностей Р,(г) мы получили бесконечную системУ дифференциальных уравнений (2) — (5). Ее решение представляет несомненные технические трудности. 4. Определение стационарного решения. В теории массового обслуживания обычно изучают лишь установившееся решение для ! — '. Существование таких решений устанавливается так называемыми эргодическими теоремами, некоторьге из них позднее будут нами установлены. В рассматриваемой задаче оказывается, что предельные или, как говорят обычно, стационарные вероятности существуют. Введем для них обозначения Р,.
Заметим дополнительно (этого мы также сейчас не станем доказывать), что Рь(1)-эО при 8 Сказанное позволяет заключить, что уравнения (3), (4), (5) для стационарных вероятностей принима2от следугощий вид: -ЛР,+ рР, =О, (б) при 1(Ь(т ЛР,, — (Л+ Ьр)Р, + (Ь + 1) ИР!~~ = О, (7) Все остальные мыслимые возможности перехода в состояние Е, за промежуток времени Ь имеют вороятность, равную о(Ь). Собрав воедино найденные вероятности, получаем следующее равенство: Р, (1+ Ь) = = Р! (1) (1 — ЛЬ вЂ” ЬОЬ)+ ЛЬР~-! (!)+(Ь+ 1) Ф2Ры ! (2) + о(Ь). Несложные преобразования приводят нас от этого равенства к такому уравнеишо для 1 < Ь < т: Р~(Г) = — (Л+ Ьр) Р„(2) + ЛР~,(!) + (Ь+ 1)рРаы(Г). (4) э ьх овслуживАнпе с ожидьнпем Так как бесконечная сумма, стоящая в квадратных скобках, сходится только при условии, что р<т, (14) то при этом предполон~ении находим равенство тл р +г Р =У + э †.ьм Ь~ а=э (15) Коли условие (14) не выполнено, т, е.
если р > т, то ряд, стоящий в квадратной скобке уравнения для определения Р„ расходится и, значит, Р, должно быть равно О. Но при этом, как следует из (12) и (13), при всех к « 1 оказывается Р, = О. Методы теории цепей Маркова позволяют заключить, что при р~т с течением времени очередь стремится к о по вероятности.
Поясним полученный результат на нескольких практических примерах, которые покажут, что обычные в практической деятельности подсчеты, основанные на чисто арифметических соображениях, при которых не учитывается специфика случайных колебаний в поступлении требований на обслуживание, приводят к серьезным просчетам. Пусть врач успевает удовлетворительно осмотреть больного и заполнить его историю болезни в среднем за 15 минут.
Планирующие органы из этого обычно делают вывод: за четырехчасовой рабочий день врач должен принимать 16 человек. Однако больные приходят в случайные моменты времени. В результате при таком подсчете пропускной способности врача к нему неизбежно скапливается очередь, так как при проведенном подсчете р принимается равным 1: Те же заключения относятся и.
к расчету числа коек в больницах, числа работающих касс в магазинах, числа официантов в ресторанах и т. д. К сожалению, некоторые экономисты совершают такую же ошибку и при расчете погрузочных средств в карьерах, числе приемщиков на элеваторах, числе причалов в морских портах и пр. Во всем дальнейшем мы предполагаем, что условие (14) выполнено. 5.
Некоторые подготовительные результаты. Во введении мы уже говорили, что для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания. Длительность ояоаданкя представляет собой случайную величину, которую обозначим буквой (. Рассмотрим сейчас только задачу определения распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания. Обозначим далее чеРез )э (7 ) 1) вероятность того, что длительность ожидания 32 гл. ь 3АдАчи ткогии массового овслужпзанпя (16) Прежде чем преобразовать эту формулу к виду, удобному для использования, приготовим некоторые необходимые нам для дальнейшего сведения.
Прежде всего для случаев ва 1 и гн 2 найдем простые формулы для Р,. Несложные преобразования приводят к таким равенствам: при т 1 Ра = 1 — р (17) а при т=2 2 — р Р а а+р' (18) Вычислим теперь вероятность того, что все приборы будут заняты в какой-то наудачу взятый момент. Очевидно, что эта вероятность равна я= «~ Рь= — ~( — ) Ра= ' . (19) Эта формула для и = 1 принимает особенно простой вид: л =р, (20) при т=2 2 2 -~- р ' (21) Напомним, что в формуле (19) р может принимать любое значение от 0 до ла (исключительно). Так что в формуле (20) р с 1, а в (21) р с 2. 6.