Механики
 Скачать 4.29 Mb.
|
|
Е 1 (1/0,0) Е 2 (2/0,0) Е 3 (1/1,0) Е 4 (1/0,1) Е 5 (2/1,0) Е 6 (2/0,1) Е 7 (1/1,1) Е 8 (2/1,1) 210 Раздел 5. Численное моделирование = + + + + + + + + + = + = = + = + + + = + = + + + = + + + + = + + + = + 1 ) ( ) ( ) ( ) ( ) ( ) ( ) ( 8 7 6 5 4 3 2 1 0 6 1 5 2 8 2 4 1 8 2 7 1 2 2 6 2 1 2 1 5 2 2 8 2 7 1 1 2 4 1 1 1 1 3 1 2 6 2 4 1 0 2 2 2 2 1 5 2 3 1 0 1 1 1 2 1 2 2 1 1 0 2 1 p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p λ λ µ λ λ µ λ µ λ λ µ λ µ µ λ µ λ λ µ λ µ µ λ µ λ λ µ µ λ µ λ λ µ µ λ λ 5. Расчет характеристик СМО . Характеристики обслуживания заявок в СМО с неоднородным потоком заявок делятся на две группы: • характеристики обслуживания заявок каждого класса; • характеристики обслуживания заявок суммарного потока. Расчёт характеристик обслуживания заявок каждого класса выполняется по следующим формулам: 1) нагрузка: 2 2 2 2 2 1 1 1 1 1 / ; / b y b y λ µ λ λ µ λ = = = = ; 2) загрузка, создаваемая заявками, которая может трактоваться как вероятность того, что на обслуживании в приборе находится заявка класса 1 и 2 соответственно: 8 6 5 2 2 7 4 3 1 1 ; ρ ρ ρ + + + = + + + = p p p p p p p ; 3) среднее число заявок в очереди: 8 7 6 4 2 8 7 5 3 1 ; p p p p l p p p p l + + + = + + + = ; 4) среднее число заявок в системе: ; 2 2 1 1 8 7 5 4 3 1 1 ρ + = + + + + + = l p p p p p p m ; 2 2 2 2 8 7 6 5 4 2 2 ρ + = + + + + + = l p p p p p p m 5) вероятность потери заявок: 8 7 6 4 2 8 7 5 3 1 ; p p p p p p p p + + + = + + + = π π ; 6) производительность по каждому классу заявок (интенсивность непотерянных заявок): ) 1 ( ); 1 ( 2 2 ' 2 1 1 ' 1 π λ λ π λ λ − = − = ; 7) среднее время ожидания заявок: ' 2 2 2 ' 1 1 1 / ; / λ λ l w l w = = 8) среднее время пребывания заявок b w m u b w m u + = = + = = 2 ' 2 2 2 1 ' 1 1 1 / ; / λ λ Расчёт характеристик обслуживания заявок суммарного потока выполняется по следующим формулам: 1) суммарная нагрузка системы: 2 1 y y Y + = ; Раздел 5. Численное моделирование 211 2) загрузка системы: 2 1 ρ ρ + = R ; 3) коэффициент простоя системы: R − = 1 η ; 4) суммарное число заявок во всех очередях: 2 1 l l l + = ; 5) суммарное число заявок в системе: R l m m m + = + = 2 1 ; 6) вероятность потери заявок: 2 1 π π π + = ; 7) производительность системы (интенсивность суммарного потока обслуженных заявок): ) 1 ( ' 2 ' 1 ' π λ λ λ λ − = + = ; 8) среднее время ожидания заявок суммарного потока: ' ' 2 ' 2 1 ' 1 / / ) ( λ λ λ λ l w w w = + = ; 9) среднее время пребывания заявок суммарного потока: b w m u u u + = = + = ' ' 2 ' 2 1 ' 1 / / ) ( λ λ λ λ 5.5. Марковские модели сетей массового обслуживания В данном параграфе подробно рассматриваются марковские модели сетей массового обслуживания (СеМО) с однородным потоком заявок. В качестве примеров представлены разомкнутые и замкнутые экспоненци- альные СеМО с накопителями ограниченной ёмкости, а также замкнутые неэкспоненциальные СеМО, в которых длительность обслуживания заявок в одном из узлов распределена по закону Эрланга с коэффициентом вариации 1 < ν и гиперэкспоненциальному закону с коэффициентом вариации 1 > ν Можно показать, что случайный процесс, протекающий в экспонен- циальных разомкнутых и замкнутых СеМО при сформулированных предположениях и допущениях является марковским. Случайный процесс, протекающий в замкнутой неэкспоненциальной сети, не является марковским. Для описания процесса функционирования такой системы в терминах марковских случайных процессов в некоторых случаях можно воспользоваться методом вложенных цепей Маркова, суть которого заключается в том, что функционирование системы рассматри- вается в определенные моменты времени, образующие цепь Маркова. Как и для СМО, в каждом примере приводится описание исследу- емой СеМО и принятые при построении математической модели предполо - жения и допущения , необходимые для того, чтобы протекающий в системе случайный процесс мог быть сведён к марковскому. Разработка Марков- ской модели включает в себя этапы кодирования состояний случайного процесса, построения размеченного графа переходов , формирования матрицы интенсивностей переходов и системы линейных алгебраических уравнений для расчёта стационарных вероятностей состояний марковского процесса, на основе которых строятся математические зависимости, позво- ляющие рассчитать наиболее важные характеристики функционирования исследуемых СеМО. 212 Раздел 5. Численное моделирование Применение марковских случайных процессов для расчёта характе- ристик функционирования и исследования свойств СеМО оказывается наиболее результативным: • для разомкнутых СеМО с накопителями ограниченной ёмкости, в которых заявки теряются при заполненных накопителях; • для неэкспоненциальных разомкнутых и замкнутых СеМО, в которых длительности обслуживания заявок в узлах распределены по гипоэкспоненциальному или гиперэкспоненциальному закону. 5.5.1. Разомкнутая экспоненциальная СеМО с накопителями ограниченной емкости Рассмотрим разомкнутую экспоненциальную СеМО с двумя однока- нальными узлами, в которую из внешней среды поступает простейший поток заявок с интенсивностью 0 λ (рис.5.16). Накопители в обоих узлах имеют ограниченную ёмкость, равную единице: 1 2 1 = = r r . Заявка, посту- пившая в узел и заставшая накопитель заполненным, теряется. Длитель- ности обслуживания в узлах распределены по экспоненциальному закону со средними значениями 1 b и 2 b соответственно. Заявки после обслужи- вания в узле 2 вероятностью q направляются в узел 1 и вероятностью ) 1 ( q − – покидают СеМО. Отметим, что, поскольку заявки в сети могут теряться, рассматрива- емая разомкнутая СеМО является нелинейной , то есть интенсивности потоков заявок, поступающих в узлы СеМО, не связаны между собой линейной зависимостью (3.5) и, следовательно, не могут быть рассчитаны путём решения системы линейных алгебраических уравнений (4.16). 1. Описание СеМО (рис.5.16) . 1.1. Сеть массового обслуживания – разомкнутая двухузловая 1.2. Узлы 1 и 2 – одноканальные: 1 2 1 = = K K 1.3. Накопители в узлах ограниченной ёмкости: 1 2 1 = = r r 1.4. Дисциплины буферизации в узлах – с потерями заявок, если накопители заполнены. 1.5. Поток заявок однородный с интенсивностью 0 λ 2. Предположения и допущения . 2.1. Поступающие в разомкнутую СеМО заявки образуют У 1 1 b 0 λ 1 1 = r ' 0 λ '' 1 λ Рис . 5.16. Двухузловая разомкнутая СеМО с потерями У 2 1 2 = r '' 2 λ 2 b q «0» «0» Раздел 5. Численное моделирование 213 простейший поток с интенсивностью 0 λ 2.2. Длительности обслуживания заявок в узлах СеМО распределены по экспоненциальному закону с параметрами, представляющими собой интенсивности обслуживания: 1 1 / 1 b = µ и 2 2 / 1 b = µ В разомкнутой СеМО при любой нагрузке существует стационарный режим, так как в узлах сети не может быть бесконечных очередей. 3. Кодирование состояний случайного процесса . Для описания состояний марковского случайного процесса будем использовать распределение заявок между узлами. Закодируем состояния следующим образом: (М 1 , М 2 ), где М i = {0, 1, 2} – количество заявок в узле i («0» – узел свободен; «1» – на обслуживании в узле находится одна заявка; «2» – в узле находятся две заявки – одна на обслуживания и вторая в накопителе). При выбранном способе кодирования система может находиться в следующих состояниях: E 0 : (0,0) – в СеМО нет ни одной заявки; E 1 : (1,0) – в узле 1 находится одна заявка; E 2 : (2,0) – в узле 1 находятся две заявки; E 3 : (0,1) – в узле 2 находится одна заявка; E 4 : (1,1) – в узле 1 и 2 находится по одной заявке; E 5 : (2,1) – две заявки находятся в узле 1 и одна – в узле 2; E 6 : (0,2) – в узле 2 находятся две заявки; E 7 : (1,2) – две заявки находятся в узле 2 и одна – в узле 1; E 8 : (2,2) – в узле 1 и 2 находятся по две заявки. 4. Размеченный граф переходов случайного процесса (рис.5.17). Построим граф переходов, полагая, что в каждый момент времени может произойти только одно событие (поступление заявки в СеМО или завершение обслуживания заявки в одном из узлов), поскольку вероятность появления двух и более событий в один и тот же момент времени равна нулю. Следует обратить внимание на переходы из состояний E 3 (0,1), E 4 (1,1), E 6 (0,2) и E 7 (1,2), обусловленные завершением обслуживания 1 µ E 0 (0,0) 2 ) 1 ( µ q − 0 λ 0 λ 0 λ 0 λ 0 λ 0 λ 1 µ 2 µ q 2 ) 1 ( µ q − 1 µ 2 µ q 2 µ 1 µ 2 µ q 2 ) 1 ( µ q − 1 µ 2 µ q 2 ) 1 ( µ q − 2 µ Рис . 5.17. Граф переходов разомкнутой СеМО с потерями 1 µ E 1 (1,0) E 2 (2,0) E 3 (0,1) E 4 (1,1) E 5 (2,1) E 6 (0,2) E 7 (1,2) E 8 (2,2) 214 Раздел 5. Численное моделирование заявки в узле 2 с интенсивностью 2 µ . В этих случаях с вероятностью q заявка может вернуться в узел 1 и с вероятностью ) 1 ( q − – покинуть СеМО, тогда интенсивности соответствующих переходов будут равны 2 µ q и 2 ) 1 ( µ q − . Если же случайный процесс находится в состояниях E 5 (2,1) и E 8 (2,2), то завершение обслуживания заявки в узле 2 приводит к переходу соответственно в состояния E 2 (2,0) и E 5 (2,1) с интенсивностью 2 µ , что соответствует выходу заявки из СеМО с вероятностью ) 1 ( q − и потере заявки, которая с вероятностью q будет направлена в узел 1, поскольку в последнем нет места в накопителе. Аналогично, если случайный процесс находится в состояниях E 7 (1,2) и E 8 (2,2), то завершение обслуживания заявки в узле 1 приводит к переходу соответственно в состояния E 6 (0,2) и E 7 (1,2) с интенсивностью 1 µ , что соответствует потере заявки, поскольку накопитель узла 1 заполнен. 5. Расчет характеристик СеМО . Не составляя матрицу интенсивностей переходов и не выписывая систему уравнений для определения стационарных вероятностей, получим математические выражения для определения узловых и сетевых характеристик разомкнутой СеМО с потерями при известных значениях стационарных вероятностей состояний ) 8 ..., , 1 , 0 ( = i p i Заметим, что СеМО с потерями относится к классу нелинейных сетевых моделей, расчёт характеристик которых связан с определёнными проблемами, в частности, с необходимостью детального анализа потоков заявок и с невозможностью применения в ряде случаев фундаментальных соотношений для расчёта сетевых характеристик. Кроме того, процесс формирования математических зависимостей для каждой конкретной нелинейной СеМО может существенно отличаться. В связи с этим, ниже достаточно подробно рассматривается процесс получения математических выражений для расчёта узловых и сетевых ха- рактеристик нелинейной разомкнутой СеМО, представленной на рис.5.16. Узловые характеристики СеМО рассчитываются в такой последовательности: 1) загрузки узлов определяются как суммы вероятностей состояний, в которых соответствующий узел занят обслуживанием заявок: 8 7 5 4 2 1 1 p p p p p p + + + + + = ρ ; 8 7 6 5 4 3 2 p p p p p p + + + + + = ρ ; 2) коэффициенты простоя узлов: 2 2 1 1 1 ; 1 ρ η ρ η − = − = ; 3) среднее число заявок в очередях: 8 5 2 1 p p p l + + = ; 8 7 6 2 p p p l + + = ; 4) среднее число заявок в узлах: 1 1 8 5 2 7 4 1 1 ) ( 2 ρ + = + + + + + = l p p p p p p m ; ; ) ( 2 2 2 8 7 6 5 4 3 2 ρ + = + + + + + = l p p p p p p m 5) производительности узлов (интенсивность обслуженных заявок на Раздел 5. Численное моделирование 215 выходе узлов): 2 2 2 2 ' 2 1 1 1 1 ' 1 ; µ ρ ρ λ µ ρ ρ λ = = = = b b ; 6) вероятности потери заявок в узлах СеМО могут быть рассчитаны на основе выражения (3.18) с учётом того, что 1 2 1 = = K K : 2 2 2 1 1 1 1 ; 1 y y ρ π ρ π − = − = ; в этих выражениях: 1 1 1 b y λ = и 2 2 2 b y λ = – создаваемые в узлах нагрузки, где 1 λ и 2 λ – интенсивности поступления заявок в узлы 1 и 2 СеМО, для расчёта которых необходимо выполнить анализ потоков в рассматриваемой СеМО; интенсивность 1 λ складывается (см. рис.5.16) из интенсивности 0 λ поступления заявок из внешнего источника и интенсивности потока заявок, возвращающихся с вероятностью q в узел 1 после обслуживания в узле 2: ' 2 0 1 λ λ λ q + = , где ' 2 λ - рассчитанная ранее интенсивность потока выходящих из узла 2 заявок (производительность узла 2); аналогично, из рис. 5.16 можно видеть, что интенсивность 2 λ поступающих в узел 2 заявок представляет собой интенсивность ' 1 λ потока выходящих из узла 1 заявок (производительность узла 1): ' 1 2 λ λ = ; окончательно, после некоторых преобразований выражения для расчёта вероятностей потери заявок в узлах СеМО примут вид: ' 1 ' 2 2 ' 2 0 ' 1 1 1 ; 1 λ λ π λ λ λ π − = + − = q ; 7) среднее время ожидания заявок в узлах рассчитывается по формулам Литтла с учётом только обслуженных заявок: ; / ; / ' 2 2 2 ' 1 1 1 λ λ l w l w = = 8) аналогично, среднее время пребывания заявок в узлах: ; / ; / 2 ' 2 2 2 1 ' 1 1 1 b w m u b w m u + = = + = = λ λ Для расчёта сетевых характеристик СеМО могут использоваться следующие формулы: 1) суммарная загрузка узлов СеМО, характеризующая среднее число одновременно работающих узлов в сети: 2 1 ρ ρ ρ + = ; 2) суммарное число заявок в очередях: 2 1 l l L + = ; 3) суммарное число заявок в узлах: ; 2 1 ρ + = + = L m m M 4) производительность СеМО (интенсивность обслуженных заявок на выходе сети): ' 2 ' 0 ) 1 ( λ λ q − = ; 5) вероятность потери заявок в сети: 0 ' 0 0 ' 0 0 1 λ λ λ λ λ π − = − = ; следует обратить внимание, что вероятность потери заявок в сети определяется как 216 Раздел 5. Численное моделирование 1 2 «0» p 12 p 10 Рис .5.18. Замкнутая СеМО 0 λ доля потерянных заявок по отношению к поступившим в СеМО заявкам, в то время как вероятности потери 1 π и 2 π заявок в узлах СеМО опреде- ляется как доля потерянных заявок по отношению ко всем заявкам, посту- пившим в конкретный узел, число которых учитывает и то, что поступив- шая в СеМО заявка за время нахождения в сети может попасть в данный узел несколько раз. Математические зависимости для расчёта суммарного времени ожидания заявок и времени пребывания заявок в СеМО не могут быть получены в общем виде в виду нелинейности СеМО с потерями. |