Исследование СМО с помощью ДИП
.pdfПростая замена реального немарковского потока на поток Эрланга еще не дает возможности использовать математический аппарат моделирования марковских процессов, так как поток Эрланга в большей или меньшей степени обладает последействием. Для того, чтобы немарковский процесс свести к марковскому применяют
Метод этапов (метод псевдосостояний).
Основа метода: отсутствие последействия у показательного распределения. Суть метода.
1)Пусть имеется устройство, в котором интервалы между событиями (процесс обслуживаниязаявок) имеют распределение, отличающееся от показательного.
2)Были определены характеристики этого потока:
- |
~ |
среднее значение интервала m 1 / μ |
-среднее квадратическое отклонение интервала ~σ
3)Были выбраны параметры k и Λ в соответствии со следующей методикой:
Если проведены измерения интервалов между событиями в потоке обслуживания или
поступления заявок, и |
полученные данные достаточны только для оценок среднего |
~ |
~ |
значенияmи дисперсии D, то можно подобрать одно распределений Эрланга с такими
же значениями математического ожидания и дисперсии. Для этого определяют значения k и Λ:
4) Заменим наше устройство другим, в котором процесс обслуживания заявок
осуществляется в k этапов, на каждом из которых интервал времени |
|||
обслуживания имеет показательное распределениесо средним временем |
~ |
1 |
. |
t |
|
||
kμ |
|||
|
|
|
При этом очередная заявка не может поступить в прибор, пока предыдущая не покинет его, пройдя все k этапов обслуживания.
Полное время обслуживания заявки представляет собой сумму k показательно распределенных интервалов, и, следовательно, распределено по закону Эрланга порядка k со средним значением
Значение k выбиралось таким образом, чтобы среднее квадратическое
отклонение интервала распределения Эрланга равнялось σ .
~
Следовательно, характеристики процессов в обоих этих устройствах совпадают. Но, и это главное, в «поэтапном» устройстве все процессы марковские и для их исследования можно использовать все рассмотренные ранее методы. Правда, кодировать состояния просто числом заявок, находящихся в данный момент в системе теперь нельзя, так как состояния будут зависеть от того, на каком из этапов обслуживания находится в этот момент процесс.
Пример – см. стр 64
Метод допускает сравнительно простое решение задачи только в случаях, когда число состояний исходной системы невелико. Однако, иногда удается применить метод и к задачам с довольно большим числом состояний для приближенного решения системы линейных алгебраических уравнений.
1. Система М/Еk/1/∞
входной поток заявок – простейший с интенсивностью λ,
поток обслуживаний – поток Эрланга порядка k с интенсивностью Λ = μ / k
( μ −интенсивность порождающего простейшего потока),
количество каналов обслуживания – 1, количество мест ожидания – не ограничено
λ |
kμ |
kμ |
… |
kμ |
|
1 |
2 |
|
k |
Система М/Еk/1/∞
Будем описывать состояние системы в определённый момент времени общим числом этапов обслуживания, через которое должны пройти все находящиеся в этот момент в системе заявки до полного завершения их обслуживания.
Если в системе n заявок, а обслуживаемая находится на i-ом этапе обслуживания, то текущее состояние: j = nk – i + 1
|
λ |
λ |
λ |
|
|
|
|
|
λ |
|
|
0 |
1 |
2 |
|
… |
k-1 |
k |
k+1 |
|
… |
2k |
… |
|
|
|
|
|
|
|
|
|
|
|
kμ |
kμ |
|
kμ |
kμ |
kμ |
kμ |
kμ |
|
kμ |
k |
||
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
ДИП для системы М/Еk/1/∞
Используя закон сохранения потоков вероятностей, строится система алгебраических уравнений для предельных вероятностей состояний:
Ввиду неограниченности мест ожидания эта система содержит бесконечное число уравнений.
НО! При выполнении условия стационарности λ/μ < 1, предельные вероятности состояний существуют и могут быть найдены.
Прием: Переходим к системе М/М/1/∞ с интенсивностью потока обслуживаний μ. Задаваясь определенной точностью, находим максимальное количество заявок, которые могут реально находиться в системе. Тем самым мы ограничиваем ДИП и систему уравнений для системы М/Еr/1/∞. Теперь эту систему можно решить и найти вероятности состояний Pi. Для дальнейшего анализа характеристик эффективности системы требуются вероятности Pi* нахождения в системе i заявок, которые можно рассчитать следующим образом:
При большом числе состояний удобно |
использовать |
для решения системы |
алгебраических уравнений метод итераций, |
равномерно |
распределив для первой |
итерации значения вероятностей состояний |
системы М/М/1/∞ между состояниями |
|
этапов системы М/Еr/1/∞. |
|
|
2. Система Еk/М/1/∞
входной поток заявок – поток Эрланга порядка k с интенсивностью Λ = λ / k
(λ −интенсивность порождающего простейшего потока),
поток обслуживаний – простейший с интенсивностью μ, количество каналов обслуживания – 1, количество мест ожидания – не ограничено
Будем предполагать, что прежде, чем попасть в систему, заявка должна пройти k этапов поступления в приемном устройстве. Время прохождения одного этапа имеет показательное распределение с интенсивностью kλ. На вход приёмного устройства поступает новая заявка, как только предыдущая появляется на его выходе. Уход из системы обслуженной заявки уменьшает суммарное число этапов поступления на k.
kλ |
kλ |
… |
kλ |
μ |
1 |
2 |
|
k |
|
Система Еk/М/1/∞
Будем описывать состояние системы общим числом этапов, через которые прошли все находящиеся в данный момент в системе заявки плюс количество этапов, пройденных вновь поступившей заявкой. Если в системе n заявок, а очередная находится на i-ом этапе, то общее число этапов поступления для всех заявок, то есть текущее состояние: j = nk + i - 1
kλ |
kλ |
|
kλ |
kλ |
kλ |
kλ |
|
kλ |
kλ |
kλ |
|
0 |
1 |
2 |
… |
k-1 |
|
k |
k+1 |
|
|
2k |
… |
|
|
… |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
μ
μ
μ
μ
ДИП для системы М/Еk/1/∞
Используя закон сохранения потоков вероятностей (сумма входящих потоков для состояния равна сумме исходящих потоков), построим систему алгебраических уравнений для предельных вероятностей состояний:
Для решения этой системы можно использовать приемы, описанные выше для системы М/Еk/1/∞. Вероятности Pi* нахождения в системе i заявок, рассчитываются следующим образом:
Немарковские СМО
До сих пор мы занимались только простейшими СМО, для которых все потоки событий, переводящие их из состояния в состояние, были простейшими. Если это условие не выполняется, то система становится немарковской.
Следует отметить, что для немарковских СМО существуют только отдельные результаты, позволяющие выразить в явном, аналитическом виде характеристики СМО через заданные условия задачи — число каналов, характер потока заявок, вид распределения времени обслуживания. Приведем некоторые из этих результатов.
1) M/G/n – n-канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания.
Ранее мы вывели формулы Эрланга для финальных вероятностей состояний СМО с отказами (М/M/n).
Б. Севастьянов доказал, что эти формулы справедливы не только при
показательном, но и при произвольном распределении |
времени |
обслуживания. |
|
2) M/G/1/∞ - одноканальная СМО с неограниченной очередью, простейшим
потоком заявок и произвольным распределением времени обслуживания
Характеристики эффективности СМО:
-поток заявок - простейший с интенсивностью λ
- время обслуживания – имеет произвольное распределение с математическим ожиданием to6 = 1/μ и коэффициентом вариации νμ
-среднее число заявок в очереди равно
где ω= λ/μ, а νμ — коэффициент вариации, т.е. отношение СКО времени обслуживания к его математическому ожиданию.
-среднее число заявок в системе
Эти формулы носят название формул Полячека — Хинчина.
-среднее время пребывания заявки в очереди
-среднее время пребывания в системе
!!!В частном случае, когда время обслуживания — показательное (νμ = 1), формулы ПолячекаХинчина превращаются в формулы для простейшей одноканальной СМО.
В частном случае, когда время обслуживания вообще не случайно (поток обслуживаний
регулярный, т.е. νμ = 0), среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем (т.к. если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании).
3) G/G/1/∞ - одноканальная СМО с произвольным потоком заявок и
произвольным распределением времени обслуживания.
Характеристики эффективности СМО:
поток заявок - произвольный рекуррентный с интенсивностью λ и коэффициентомвариации νλ интервалов между заявками, 0 < νλ < 1.
- время обслуживания – имеет произвольное распределение с математическим ожиданием to6 = 1/μ и коэффициентом вариации νμ
Для этого случая точных аналитических формул получить не удается; можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу. Грубо приближеннаяоценка
-средняя длина очереди
- среднее число обслуживаемых заявок