Механики
 Скачать 4.29 Mb.
|
|
закона сохранения суммарной длины очереди заявок: ДО 1 Const L w H i i i ∑ = = = λ Таким образом, если средние длительности обслуживания заявок разных классов одинаковы, то изменение ДО не приводит к изменению суммарной длины L очередей заявок всех классов, которая остается постоянной. В то же время длины очередей ) , 1 ( H i l i = заявок каждого класса меняются с изменением ДО. 4.4. Разомкнутые экспоненциальные СеМО с однородным потоком заявок « Чем сложнее и грандиознее план, тем больше шансов, что он провалится» (Производная от закона Мэрфи) 4.4.1. Описание разомкнутых СеМО Рассмотрим разомкнутую экспоненциальную сеть массового обслуживания (СеМО) с однородным потоком заявок при следующих предположениях: 1) разомкнутая СеМО (РСеМО) произвольной топологии содержит n узлов; 2) после завершения обслуживания в каком-либо узле передача заявки в другой узел происходит мгновенно; 3) в качестве узлов могут быть как одноканальные, так и многоканальные СМО; 4) все приборы многоканального узла являются идентичными, и любая заявка может обслуживаться любым прибором; 5) заявка, поступившая в многоканальный узел, когда все или несколько приборов свободны, направляется случайным образом в любой свободный прибор; 6) в каждом узле РСеМО имеется накопитель заявок неограниченной ёмкости, что означает отсутствие отказов поступающим заявкам при их постановке в очередь, то есть любая поступающая в узел заявка всегда Раздел 3. Аналитическое моделирование 139 найдет в накопителе место для ожидания независимо от того, сколько заявок уже находится в очереди; 7) заявки поступают в РСеМО из внешнего независимого источника и образуют простейший поток заявок; 8) длительности обслуживания заявок во всех узлах сети представ- ляют собой случайные величины, распределенные по экспоненциальному закону; 9) обслуживающий прибор любого узла не простаивает, если в его накопителе имеется хотя бы одна заявка, причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка; 10) в каждом узле сети заявки из накопителя выбираются в соответствии с бесприоритетной дисциплиной обслуживания в порядке поступления (ОПП) по правилу «первым пришел – первым обслужен» (FIFO – First In First Out). Для описания линейных разомкнутых однородных экспоненциальных СеМО необходимо задать следующую совокупность параметров: • число узлов в сети: n; • число обслуживающих приборов в узлах сети: n K K ..., , 1 ; • матрицу вероятностей передач: ] , , 1 , 0 , [ n j i p ij K = = P , где вероятности передач ij p должны удовлетворять условию (3.23): сумма элементов каждой строки должна быть равна 1; • интенсивность 0 λ источника заявок, поступающих в РСеМО; • средние длительности обслуживания заявок в узлах сети: n b b , , 1 K На основе перечисленных параметров могут быть рассчитаны узловые и сетевые характеристики, описывающие эффективность функционирования соответственно узлов и РСеМО в целом. Расчет характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО базируется на эквивалентном преобразовании сети и проводится в четыре этапа: • расчет коэффициентов передач j α и интенсивностей потоков заявок j λ в узлах n j , 1 = СеМО; • проверка условия отсутствия перегрузок в СеМО; • расчет узловых характеристик; • расчет сетевых характеристик. 140 Раздел 3. Аналитическое моделирование 4.4.2. Расчет коэффициентов передач и интенсивностей потоков заявок в узлах РСеМО Покажем, что интенсивности n λ λ , , 0 K потоков заявок, поступающих в узлы n ..., , 0 сети, однозначно определяются вероятностями передач ) , , 1 , ( n j i p ij K = , задающими маршруты заявок в СеМО. Будем рассматривать только установившийся режим. Так как в линейной СеМО заявки не размножаются и не теряются, то интенсивности входящего и выходящего потоков для любого узла будут равны между собой. Интенсивность потока заявок, входящих в любой узел j сети, равна сумме интенсивностей потоков заявок, поступающих в него из других узлов n i , 0 = (рис.4.11). Поскольку заявки из узла i поступают в узел j с вероятностью ij p , то интенсивность потока заявок, поступающих из i в j , равна i ij p λ , где i λ - интенсивность выходящего и, следовательно, входящего потока заявок узла i . С учетом этого, на входе узла j имеется поток с интенсивностью ∑ = = = n i i ij j n i p 0 ) , , 1 , 0 ( K λ λ . (4.16) Выражение (4.16) представляет собой систему линейных алгебраи- ческих уравнений ) 1 ( + n -го порядка, из которой могут быть найдены интенсивности потоков заявок в виде соотношения ) , 1 ( 0 n j j j = = λ α λ Коэффициент j α называется коэффициентом передачи и определяет среднее число попаданий заявки в узел j за время ее нахождения в сети, причем 1 0 = α Для разомкнутой СеМО известна интенсивность источника заявок 0 λ . Можно показать, что система уравнений для расчета интенсивностей имеет единственное решение вида 0 λ α λ j j = , где 0 λ – заданная величина. i j i λ i i p λ 0 i i p λ 1 i ij p λ i in p λ " 0 " " 1 " " "n i ij p λ j λ 0 0 λ j p 1 1 λ j p n nj p λ " 0 " " 1 " " "n Рис.4.11. К расчёту интенсивностей потоков заявок в узлах РСеМО Раздел 3. Аналитическое моделирование 141 4.4.3. Проверка условия отсутствия перегрузок в СеМО В п.3.4.2 показано, что в разомкнутой СеМО отсутствуют перегрузки, если выполняется условие (3.25): < n n n b K b K b K α α α λ ,..., , min 2 2 2 1 1 1 0 Если указанное условие не выполняется, то, как следует из него, стационарный режим в разомкнутой СеМО может быть реализован одним из следующих способов: • уменьшением интенсивности 0 λ внешнего источника заявок до значения, при котором это условие будет выполняться; • увеличением количества обслуживающих приборов j K в перегруженных узлах; • уменьшением длительностей j b обслуживания заявок в перегруженных узлах; • уменьшением коэффициентов передач j α в перегруженных узлах. 4.4.4. Расчет узловых характеристик РСеМО Один и тот же объект, рассматриваемый на разных уровнях детализации, можно представить различными моделями массового обслуживания, характеристики которых одинаковы или отличаются на величину, не превосходящую заданной погрешности. При выполнении определенных условий такие модели легко преобразуются друг в друга. Для сетевых моделей в виде разомкнутых и замкнутых СеМО могут использоваться два вида преобразований: • эквивалентное преобразование; • толерантное преобразование. Две сетевые модели эквивалентны, если сравниваемые характеристики этих моделей не отличаются друг от друга. Две сетевые модели толерантны (подобны), если значения определенных характеристик отличаются друг от друга на величину, не превосходящую заданную. Использование свойств эквивалентных и толерантных моделей позволяет упростить расчет характеристик моделей путем замены сложных сетевых моделей более простыми. Эквивалентными могут быть сетевые модели одного типа (например, две замкнутые сети), толерантными — модели как одного, так и разных типов [11]. Расчет характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО базируется на эквивалентном преобразовании сети, заключающемся в представлении разомкнутой СеМО с n узлами в виде n независимых экспоненциальных СМО типа 142 Раздел 3. Аналитическое моделирование M/M/N (простейший поток заявок, длительность обслуживания распределена по экспоненциальному закону, N обслуживающих приборов). При этом интенсивность входящего потока заявок в СМО, отображающую узел ) , 1 ( n j j = сети, определяется из системы алгебраических уравнений (4.16) через интенсивность входящего в сеть потока и коэффициент передачи узла: 0 λ α λ j j = , а средняя длительность обслуживания заявок в СМО равна длительности обслуживания j b заявок в соответствующем узле СеМО. Характеристики всех n СМО (время ожидания заявок в очереди и пребывания в системе, длина очереди и число заявок в системе, среднее число занятых приборов и т.д.) представляют собой узловые характеристики СеМО. Среднее время ожидания заявок в очереди может быть рассчитано с использованием выражения (4.8) для многоканальных СМО типа M/M/N или выражения (4.1) для одноканальных СМО типа M/M/1, остальные характеристики узла ) , 1 ( n j j = – с использованием фундаментальных соотношений, представленных в п.3.4.3, а именно: • нагрузка в узле j, показывающая среднее число занятых приборов: j j j b y λ = ; • загрузка узла j: ) 1 ; / ( min j j j K y = ρ , где j K – число обслуживающих приборов в узле j; • коэффициент простоя узла: j j ρ π − = 1 ;;;; • время пребывания заявок в узле: j j j b w u + = ; • длина очереди заявок: j j j w l λ = ; • число заявок в узле (в очереди и на обслуживании в приборе): j j j u m λ = Рассчитанные таким образом характеристики отдельных СМО в точности соответствуют узловым характеристикам исходной СеМО, то есть в отношении своих характеристик модель массового обслуживания, представляющая собой совокупность независимых СМО (каждая СМО рассматривается независимо от других), строго эквивалентна исходной разомкнутой СеМО в целом. 4.4.5. Расчет сетевых характеристик РСеМО Сетевые характеристики, описывающие эффективность функционирования СеМО в целом, рассчитываются на основе полученных значений узловых характеристик. В состав сетевых характеристик входят: • среднее число заявок, ожидающих обслуживания в сети, и среднее число заявок, находящихся в сети: Раздел 3. Аналитическое моделирование 143 ∑ = = n j j l L 1 ; ∑ = = n j j m M 1 , где j l – средняя длина очереди и j m – среднее число заявок в узле j; • среднее время ожидания и среднее время пребывания заявок в сети: ∑ = = n j j j w W 1 α ; ∑ = = n j j j u U 1 α , где j w и j u – соответственно среднее время ожидания и среднее время пребывания заявок в узле j; j α – коэффициент передачи для узла j, показывающий среднее число попаданий заявки в узел j за время ее нахождения в сети. Пример 4.2. Проиллюстрируем изложенный метод расчета харак- теристик функционирования линейных разомкнутых однородных экспо- ненциальных СеМО на примере СеМО с четырьмя узлами ( 4 = n ), граф которой представлен на рис.4.12. Связи между узлами СеМО описываются следующей матрицей вероятно- стей передач: 0 0 0 1 0 4 1 0 0 0 0 3 1 0 0 0 0 2 0 7 , 0 2 , 0 0 1 , 0 1 0 0 0 1 0 0 4 3 2 1 0 = P В РСеМО поступает простейший поток заявок с интенсивностью 1 0 с 1 , 0 − = λ Положим , что все узлы СеМО – одноканальные , а средние длительности обслуживания заявок в узлах соответственно равны : 8 , 0 1 = b с ; 2 2 = b с ; 4 , 0 3 = b с ; 3 , 0 4 = b с Система линейных алгебраических уравнений для расчёта интенсивностей потоков заявок в узлах СеМО , согласно (4.16), имеет вид : + = + = = = = = + = + = = = 3 2 3 34 2 24 4 1 1 13 3 1 1 12 2 4 0 4 41 0 01 1 1 1 10 0 7 , 0 2 , 0 1 , 0 λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ p p p p p p p Решая эту систему уравнений , получим следующие значения интенсивностей : 1 1 с 1 − = λ , 1 2 с 2 , 0 − = λ , 1 3 с 7 , 0 − = λ , 1 4 с 9 , 0 − = λ Тогда 2 3 12 p 10 p 1 13 p Рис.4.12. Граф разомкнутой СеМО 0 λ «0» 144 Раздел 3. Аналитическое моделирование коэффициенты передач будут равны : 10 / 0 1 1 = = λ λ α ; 2 / 0 2 2 = = λ λ α ; 7 / 0 3 3 = = λ λ α ; 9 / 0 4 4 = = λ λ α Определим предельную интенсивность поступления заявок в разомкнутую СеМО , при которой в сети отсутствуют перегрузки Для этого воспользуемся выражением (3.25), определяющим условие отсутствия перегрузок в РСеМО : 1 4 4 4 3 3 3 2 2 2 1 1 1 0 с 125 , 0 , , , min − = < b K b K b K b K α α α α λ РСеМО работает без перегрузок , поскольку данное условие выполняется В соответствии с эквивалентным преобразованием представим рассматриваемую экспоненциальную разомкнутую СеМО в виде 4- х независимых СМО типа M/M/1, в которые поступают простейшие потоки заявок соответственно с интенсивностями : 1 1 с 1 − = λ , 1 2 с 2 , 0 − = λ , 1 3 с 7 , 0 − = λ , 1 4 с 9 , 0 − = λ , а средние длительности обслуживания заявок в СМО совпадают с длительностями обслуживания в соответствующих узлах СеМО : 8 , 0 1 = b с ; 2 2 = b с ; 4 , 0 3 = b с ; 3 , 0 4 = b с Значения узловых характеристик СеМО , рассчитанные с использованием выражения (4.1) для среднего времени ожидания заявок в очереди СМО типа M/M/1 и фундаментальных соотношений , представлен - ных в п .3.4.3, приведены в табл .4.1. Таблица 4.1 Узловые характеристики Расчётные формулы Узел 1 Узел 2 Узел 3 Узел 4 Нагрузка j j j b y λ = 0,8 0,4 0,28 0,27 Загрузка ) 1 ; / ( min j j j K y = ρ 0,8 0,4 0,28 0,27 Коэф - т простоя j j ρ π − = 1 0,2 0,6 0,72 0,73 Время ожидания ) 1 /( j j j j b w ρ ρ − = 3,2 1,33 0,16 0,11 Время пребывания j j j b w u + = 4 3,33 0,56 0,41 Длина очереди j j j w l λ = 3,2 0,27 0,11 0,10 Число заявок в узле j j j u m λ = 4 0,67 0,39 0,37 В табл .4.2 представлены математические зависимости и полученные на их основе значения сетевых характеристик , рассчитанные с учётом найденных значений узловых характеристик |