The 16 reference contexts in paper Yu. Nesterov G., Ю. Нестеров Г. (2016) “Декомпозиционный метод анализа замкнутых сетей массового обслуживания // Decomposition method for analysis of closed queuing networks” / spz:neicon:technomag:y:2014:i:2:p:263-276

  1. Start
    675
    Prefix
    которых, в отличие от разомкнутых СеМО, популяция заявок фиксирована, широко используются в качестве моделей для оценки временных характеристик информационных систем, а также других систем массового обслуживания, например в торговле, логистике и т.п. [ 1, 2]. Получено большое количество результатов для конкретных, частных типов замкнутых СМО и СеМО
    Exact
    [2-5,14-19]
    Suffix
    . Однако до сих пор не существует общих аналитических методов, пригодных для анализа широкого класса таких сетей. Метод имитационного моделирования, являясь универсальным инструментом анализа подобных систем, тем не менее не лишен ряда недостатков.
    (check this in PDF content)

  2. Start
    1532
    Prefix
    СМО, неизвестные параметры которых связаны системой нелинейных уравнений баланса; - доказательстве существования решения полученной системы уравнений; - нахождении решения полученной системы уравнений модифицированным методом Ньютона-Канторовича. Постановка задачи. Рассмотрим класс замкнутых СеМО, описываемый кортежем S: S = < L, R, P, N, B, D, β, δ, γ > (1). здесь: L=
    Exact
    [1, L]
    Suffix
    - множество индексов узлов СеМО, L- число узлов. Узел СеМО представляет собой один или несколько обслуживающих аппаратов (ОА), очередь перед ним(и) и соответствующую дисциплину обслуживания заявок из этой очереди.
    (check this in PDF content)

  3. Start
    1755
    Prefix
    Рассмотрим класс замкнутых СеМО, описываемый кортежем S: S = < L, R, P, N, B, D, β, δ, γ > (1). здесь: L= [1, L] - множество индексов узлов СеМО, L- число узлов. Узел СеМО представляет собой один или несколько обслуживающих аппаратов (ОА), очередь перед ним(и) и соответствующую дисциплину обслуживания заявок из этой очереди. R=
    Exact
    [1,R]
    Suffix
    - множество индексов классов заявок в СеМО, R – число классов. P= { Pr} – множество стохастических квадратных матриц Pr размером LxL, здесь и далее верхний индекс r означает номер класса заявки, r ∈ R .
    (check this in PDF content)

  4. Start
    2534
    Prefix
    N=(N1, N2,...,Nr,...,NR) - вектор популяции заявок, 1≤Nr - число заявок класса ‘r’, натуральное число. B - множество функций распределения вероятностей (ФРВ) с конечным первым моментом, что является достаточным условием существования стационарного режима в СеМО
    Exact
    [3]
    Suffix
    . D – множество дисциплин обслуживания заявок в узлах СеМО, имеющих консервативный характер, т.е. сохраняющих проделанную работу (например, абсолютные приоритеты с дообслуживанием прерванных заявок, относительные приоритеты, первый пришел - первым обслужен, различные виды циклического обслуживания с квантованием времени и без него, немедленное обслуживание, когда числ
    (check this in PDF content)

  5. Start
    4804
    Prefix
    В итоге исходная сеть S декомпозируется на L замкнутых СМО типа MR/GIR/n//NR в обозначениях Кендалла [ 7 ], т.е. на L замкнутых СМО типа модели ремонтника. Подобные замкнутые СМО достаточно хорошо изучены, см., например,
    Exact
    [6]
    Suffix
    . Для целей нашего исследования назовем эти модели базовыми. Система уравнений баланса. Выделим в сети узел ‘j’ ( j∈L ), заметим какую-либо заявку класса ‘r’ (r∈R) и проследим процесс ее блуждания по той части сети, которая состоит из узлов L \ j, в течение интервалов времени между последовательными посещениями этой заявкой узла ‘j’.
    (check this in PDF content)

  6. Start
    6135
    Prefix
    Здесь: li Vir- время пребывания меченой заявки класса ‘r’ в узле ‘i’ при li-м его посещении в течение времени lrA. j Kir - число посещений меченой заявкой класса ‘r’ узла ‘i’ за время lrA. j Kir суть случайная величина, не зависящая от { li Vir} и принимающая значения 0,1,2,.... Переходя к средним значениям и используя теорему Колмогорова-Прохорова
    Exact
    [8, с.188]
    Suffix
    , получим из (2): (L\ j) j jrir ir i akv ∈ =∑ (3). Здесь jra, jirk и irv суть математические ожидания случайных величин lrA, j Kir и li Vir соответственно. Величину j kir - среднее число посещений меченой заявкой класса ‘r’ узда ‘i’, приходящееся на одно посещение узла ‘j’, определим следующим образом.
    (check this in PDF content)

  7. Start
    7493
    Prefix
    Число пребываний цепи в состоянии “i” в расчете на одно пребывание в состоянии “j” равно /rrijNN. Нетрудно видеть, что lim (/)lim (/) / lim (/)/ r rr jrrrrrr rr kirijijijN NNNNNNNNππ→∞→∞→∞=== (4). Подставляя (4) в (3) получим: L\ j jr(/) ,
    Exact
    [1, , , , ]
    Suffix
    ,[1,..., ]rrijir i av jLrRππ ∈ =∈∈∑ (5). Заметим, что (5) впервые было приведено в работе [9] без доказательства. Сделаем допущение о том, что jrA распределено по экспоненциальному закону с параметром 1 λjrjra − =.
    (check this in PDF content)

  8. Start
    7594
    Prefix
    Нетрудно видеть, что lim (/)lim (/) / lim (/)/ r rr jrrrrrr rr kirijijijN NNNNNNNNππ→∞→∞→∞=== (4). Подставляя (4) в (3) получим: L\ j jr(/) ,[1, , , , ],[1,..., ]rrijir i av jLrRππ ∈ =∈∈∑ (5). Заметим, что (5) впервые было приведено в работе
    Exact
    [9]
    Suffix
    без доказательства. Сделаем допущение о том, что jrA распределено по экспоненциальному закону с параметром 1 λjrjra − =. Это означает замену дополнения узла ‘j’ до сети источником конечной емкости с экспоненциальным распределением времени пребывания в источнике, причем средние времена преб ывания заявок всех классов в источнике и в дополнении узла “j” до
    (check this in PDF content)

  9. Start
    9563
    Prefix
    RRiiRLLRν ν νν ν ν ν ν ν=, оператор 1111(,...,,...,,...,)RLLRθθ θ θ θ=    суть -отображение lRLR RR++→ ν θνir( ),ir= 1,..., ,iL= 1,...,rR= Или ()()0φν θν ν= −=, (9) что эквивалентно (7) и (8). В силу сложности выражений для оператора θрешение следует искать среди итерационных методов. При отыскании решения (8,9) возникают три проблемы
    Exact
    [10]
    Suffix
    , а именно: 1. Доказательство существования решения системы уравнений; 2. Конструирование метода отыскания решения; 3. Доказательство сходимости метода. Докажем, что решение системы уравнений (8) существует.
    (check this in PDF content)

  10. Start
    10933
    Prefix
    Из (12) следует, что ()BBθ⊂, т.е. оператор θ отображает множество В в себя, причем имеет место строгое включение. Непрерывность отображения : BBθ→ следует из непрерывности функций (5( и (6). Следовательно оператор θ удовлетворяет на В условиям теоремы Брауэра
    Exact
    [11]
    Suffix
    , т.е. имеет в В неподвижную точку * ν, которая и есть решение системы уравнений (8). Что и требовалось доказать. Монотонность функций 12(,,...,,...,)iririiiriRvaaaaθ= по каждой из переменных ira и аддитивный характер зависимости j ( \) ir(/)rrjijr Li avππ ∈ =∑ дают основание полагать, что решение системы (8) единственное.
    (check this in PDF content)

  11. Start
    11415
    Prefix
    Монотонность функций 12(,,...,,...,)iririiiriRvaaaaθ= по каждой из переменных ira и аддитивный характер зависимости j ( \) ir(/)rrjijr Li avππ ∈ =∑ дают основание полагать, что решение системы (8) единственное. Однако вопрос доказательства единственности решения пока остается открытым. Конструирование метода решения системы уравнений (8). В
    Exact
    [9]
    Suffix
    для решения подобного типа уравнений предлагается метод простых итераций, а качестве начального приближения используется вектор средних значений времен обслуживания заявок в узлах: ν011121211(,.
    (check this in PDF content)

  12. Start
    12072
    Prefix
    RRiiRLLRb bb bb b bb= При этом ошибочно утверждается, что итерационный процесс ν θνkk(1),1, 2, 3,...k−==  сходится в общем случае, а достаточным условием сходимости является выполнение условий: 1). 0ir ajk ∂θ < ∂ - монотонное убывание irν от jka и 2). 2 20 ir ajk ∂θ ≠ ∂ - отсутствие точек перегиба по jka. Покажем, что l−∞ норма
    Exact
    [10]
    Suffix
    матрицы Якоби [ J ] для оператора θ уравнения (8) может быть больше 1. Действительно ir, ,1,..., , ,1,...,irik jkikjkLRxLRLRxLR a Ji jL rkR a θθ ∞νν ∞∞   ∂∂∂ ====     ∂∂∂    Для базовых СМО с абсолютными приоритетами имеем: ( ,()1,..., ) (0)()(0)irir ikik k rkrRk rk r aa θθ∂∂ ∀ ∀=> →= ∧ ≤ → −∞ < < ∂∂ ,
    (check this in PDF content)

  13. Start
    13172
    Prefix
    rrR a ∂θ ∀= ∃ = ∀ =< ∂ и всегда найдется такая матрица P r = [p r ij]LxL , что будет иметь место следующее соотношение, означающее наличие в СеМО для заявок приоритета k «редко» посещаемого узла j: 1 () k iir k jika πθ π − ∂ > ∂ . А это значит, что норма 1J∞> и, следовательно, не выполняются достаточные условия сходимости метода простых итераций
    Exact
    [12]
    Suffix
    для уравнения (8). Таким образом, для нахождения решения системы уравнений (8) необходимо использовать итерационный метод более «высокого» порядка. Метод решения системы нелинейных уравнений (8).
    (check this in PDF content)

  14. Start
    13744
    Prefix
    Из того факта, что система (8) эквивалентна системе (9), а также из монотонности и выпуклости зависимостей ()irirjkν θν= и линейного аддитивного характера зависимости (5) , след ует, что оператор ()()0φν θν ν= −= удовлетворяет на B условиям теоремы Канторовича
    Exact
    [12, с.491]
    Suffix
    . Таким образом, для нахождения решения системы уравнений (9) и эквивалентной ей системы (8) можно применить метод Ньютона-Канторовича [13], использующий обращение матрицы производных Фреше оператора ()φν и обеспечивающий быструю (квадратичную) сходимость: [] 1 ν ν φ ν φνnn1( )( ), 0,1, 2, ...nnn − +′=−= здесь ()nφν′ - производная Фр
    (check this in PDF content)

  15. Start
    13911
    Prefix
    и выпуклости зависимостей ()irirjkν θν= и линейного аддитивного характера зависимости (5) , след ует, что оператор ()()0φν θν ν= −= удовлетворяет на B условиям теоремы Канторовича [12, с.491]. Таким образом, для нахождения решения системы уравнений (9) и эквивалентной ей системы (8) можно применить метод Ньютона-Канторовича
    Exact
    [13]
    Suffix
    , использующий обращение матрицы производных Фреше оператора ()φν и обеспечивающий быструю (квадратичную) сходимость: [] 1 ν ν φ ν φνnn1( )( ), 0,1, 2, ...nnn − +′=−= здесь ()nφν′ - производная Фреше. (16) Учитывая тот факт, что основные затраты машинного времени приходятся на вычисление обратной матрицы [] 1 φν()n − ′ , для сокращения времен
    (check this in PDF content)

  16. Start
    15959
    Prefix
    Обосновано, что в качестве метода решения полученной системы уравнений баланса следует использовать модифицированный метод Ньютона-Канторовича, обеспечивающий быструю сходимость итерационной процедуры. 4. Возможности данного метода ограничены перечнем известных на сегодня аналитических или численных решений для моделей типа модели ремонтника
    Exact
    [6]
    Suffix
    , а также возможностями численного решения нелинейных уравнений типа (8) и (9). Метод НьютонаКанторовича основан на обращении матриц, что поддерживается, например, в таких программных системах как MatLab и MathCAD.
    (check this in PDF content)