A queuing system with distinct devices as the finite state machine

Full Text

Актуальность и постановка задачи исследования. Целью настоящей работы является разработка описания и имитационного моделирования систем массового обслуживания (СМО) с неоднородными приборами с раздельными накопителями с запретом передачи заявок из одного накопителя в другой. В то время как большинство СМО, встречающихся на практике, можно отнести к системам с раздельными очередями, их моделированию посвящено лишь несколько работ. Для систем с многосекционной памятью в [1] моделируется 4-канальная СМО с двумя типами приборов (по две пары однородных приборов). Каждая заявка обслуживается обоими типами приборов; выбор прибора из пары однородных случаен. При этом отсутствует постановка задачи в формулировке как теории массового обслуживания (ТМО), так и математической статистики, например, отсутствуют данные о законе распределения. В работе [2] отмечена актуальность исследования СМО с раздельными очередями к приборам при различных дисциплинах обслуживания, а также тот факт, что аналитические методы ТМО плохо распространяются на системы данного типа, особенно в случае большого числа приборов N , когда использование численных методов затруднительно. Авторы рассматривают систему с N приборами и диспетчеризацией, которая предполагает, что приборы имеют одинаковую производительность, т.е. однородны. В работе [3] рассматривается подобная система с N приборами с раздельными очередями, однако заявки представляются в форме сообщения из n пакетов, каждый из которых посылается на случайно выбранный прибор, что также не соответствует общему случаю, рассматриваемому в настоящей статье. В более общем случае [4, 5] система с раздельными очередями рассматривалась в контексте исследования приоритетного обслуживания. Наиболее полное развитие аналитические модели СМО с неоднородными Андрей Петрович Котенко (к.ф.-м.н., доц.), доцент, каф. прикладной математики и информатики. Максим Борисович Букаренко, аспирант, каф. прикладной математики и информатики. 114 Сиситема массового обслуживания с различимыми каналами как конечный автомат приборами и общей очередью получили в работах В. В. Рыкова и Д. В. Ефросинина в рамках общей теории управляемых систем обслуживания. В работе [6] ставится задача существования оптимальной политики с точки зрения динамического программирования, однако в [7] показана неполнота этого доказательства. Системы массового обслуживания с раздельными очередями и неоднородными приборами удалось аналитически смоделировать только в случае либо детерминированного входящего потока, либо «упорядоченного входа», когда заявка встаёт в очередь на обслуживание к первому прибору со свободным местом в очереди [8, 9]. В таких системах диспетчеризация не зависит от состояния системы в момент поступления заявки. Таким образом, очевидна необходимость исследования СМО с различимыми каналами, наиболее точно отражающими реальные процессы, которые не всегда подчиняются аксиоматике процессов гибели и размножения. В нотификации [10, 11] рассмотрим систему массового обслуживания с различимыми каналами (имеющими, к примеру, разную пропускную способность или раздельные очереди) сигнатуры T = T (µ1 , µ2 , . . . , µk ; m1 , m2 , . . ., mk ), где µi — пропускная способность, mi — число мест в очереди i-того канала, i ∈ 1, k; k >0. Оптимизация работы системы по среднему времени обслуживания заявок и минимизации вероятности отказа достигается с помощью следующего протокола диспетчеризации входных заявок. Пусть очередная входная заявка обнаруживает систему в состоянии (x1 , x2 , . . . , xk ; y1 , y2 , . . . , yk ), не являющемся состоянием отказа (1, 1, . . . , 1; m1 , m2 , . . . , mk ), где xi = 1, если i-тый канал занят, xi = 0, если свободен, yi соответствует наполненности очереди этого канала. В первом случае, если существует один и только один канал (с номером i), способный принять заявку (0 yi |xi mi − 1|), то заявка направляется к нему. В противном случае оптимальным считаем выбор i-того канала обслуживания, способного обработать заявку с минимальным средним суммарным временем T обслуживания попавших в него заявок: T = min i:0 yi |xi mi −1| µ−1 (yi + 1 + χi ), i (1) где χi — случайная величина, характеризующая незавершённость обработки заявки, находящейся в i-том канале в момент поступления новой заявки, 0 χi 1. Для простоты примем χi = 1. СМО с детерминированной диспетчеризацией и недетерминированной выработкой сигналов на освобождение приборов. Далее рассмотрим двухканальную СМО с различимыми каналами пропускной способности µ1 > µ2 без очереди (сигнатура T = T (µ1 , µ2 ; 0, 0) в нотификации [1, 2]). Представим её поведение в дискретном времени n ∈ 0, +∞ через недетерминированный конечный автомат (НКА) K(S, A) с алфавитом внутренних состояний S = = {(00), (01), (10), (11)} без выделенных начального и конечного состояний, входным алфавитом A = {0,1} и пустым выходным алфавитом. Буква 1 входного алфавита A соответствует приходу заявки в систему, а 0 — выработке сигнала освобождения заявки одним из каналов. Матрица переходов автомата K(S, A) с учётом возможной диспетчеризации (1) и недетерминированного выбора переходов (11) → (10) и (11) → (01) приведена в табл. 1. 115 К о т е н к о А. П., Б у к а р е н к о М. Б. Таблица 1 Матрица переходов НКА K(S, A) с четырьмя стохастическими дугами S\A 0 1 (10) (01) (00) (00) p1 p2 (01) (00) (11) (10) (00) (11) (10) (01) (11) (11) q1 q2 Здесь p1 — вероятность перехода по стохастической дуге (00) → (10) в соответствии с оптимальной диспетчеризацией (1), p2 = 1 − p1 — дополнительная вероятность перехода по стохастической дуге (00) → (01). При этом входная заявка, заставшая систему в состоянии простоя обоих каналов (00), выбирает каналы 1 или 2 с частотами p1 > 0 и p2 = 1 − p1 > 0 соответственно. Аналогично, q1 — вероятность перехода по стохастической дуге (11) → (10) при освобождении заявки каналом 1, q2 = 1 − q1 — дополнительная вероятность перехода по стохастической дуге (11) → (01) при освобождении заявки каналом 2. При этом уход обработанной (выходной) заявки из системы, находившейся в состоянии отказа (10), переводит систему в состояния (10) или (01) с частотами q1 > 0 и q2 = 1 − q1 > 0 соответственно. Остальные дуги орграфа нестохастические; переход по ним осуществляется при поступлении соответствующего входного сигнала. На рис. 1 представлен граф переходов НКА K(S, A) при детерминированной оптимальной диспетчеризации (1). Здесь и на других рисунках разметкой α : β помечены стохастические дуги, переход по которым происходит с вероятностью β при получении входного сигнала α. Детерминированные петли описывают следующие переходы: (11) → (11) — приход входной заявки (входного сигнала 1) в систему, находящуюся в состоянии отказа (11); (00) → (00) — приход входного сигнала 0 в систему, находящуюся в состоянии простоя (00). Второй вариант можно считать «холостым ходом» в работе СМО, которая была способна совершить обработку выходной заявки, но таковой не оказалось на месте в данный момент времени. В случае недетерминированной оптимизации (1), допускающей переход части входных заявок по неоптимальной дуге (00) → (01), уравнения состояний S(n + 1) = (s1 (n + 1), s2 (n + 1)) автомата K(S, A) получим из таблицы истинности булевых функций s1 (n + 1) и s2 (n + 1) (табл. 2). Рис. 1. Граф переходов НКА K(S, A) с двумя стохастическими дугами (11) → (10) и (11) → (01) 116 Сиситема массового обслуживания с различимыми каналами как конечный автомат Таблица 2 Таблица истинности стохастических булевых функций s1 (n + 1) и s2 (n + 1) НКА K(S, A) с четырьмя стохастическими дугами a(n) s1 (n) s2 (n) s1 (n + 1) s2 (n + 1) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 q1 q2 q1 q2 1 0 0 1 1 0 0 p1 p2 p1 p2 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 Далее рассмотрим три случая сочетания стохастической природы дуг орграфа, представленные недетерминированными конечными автоматами. При детерминированной диспетчеризации входных заявок с протоколом (1) имеем вероятности p1 = 1, p2 = 0. Тогда получим для a = a(n), s1 = = s1 (n), s2 = s2 (n) нелинейные нестационарные рекурсивные стохастические булевы функции в правой части уравнений состояний НКА K(S, A) с двумя оставшимися недетерминированными переходами (11) → (10) и (11) → (01): s1 (n + 1) = a ⊕ s1 s2 ⊕ as1 s2 a , q1 q2 (2) s2 (n + 1) = a ⊕ as1 ⊕ as1 s2 a ⊕ s1 s2 ⊕ as1 . q1 q2 (3) Из (2) следует линейное явное (то есть не рекурсивное) детерминированное (то есть не стохастическое) нестационарное необходимое, но не достаточное условие a(n) a(n) a(n)s1 (n + 1) = = a(n), q1 q2 эквивалентное числовому линейному явному нестационарному неравенству s1 (n + 1) a(n), которое легко усмотреть из сравнения соответствующих столбцов табл. 2. Аналогично, из (3) получим нелинейное рекурсивное нестационарное необходимое, но не достаточное стохастическое условие s1 (n)s2 (n + 1) = a(n)s1 (n)s2 (n) s1 (n)s2 (n) , q1 q2 из которого следует нелинейное (квадратичное) рекурсивное детерминированное нестационарное необходимое, но не достаточное условие a(n)s1 (n)s2 (n + 1) = a(n)s1 (n)s2 (n) a(n)s1 (n)s2 (n) = a(n)s1 (n)s2 (n), q1 q2 эквивалентное утверждению a(n)s1 (n) = 1 ⇒ s2 (n + 1) = s2 (n). Это линейное равенство также легко усмотреть из сравнения соответствующих столбцов и строк табл. 2. 117 К о т е н к о А. П., Б у к а р е н к о М. Б. Таблица 3 K(S, A1 ) 10 (10) (11) (11) (11) Избавимся от стохастичности дуг (11) → (10) и (11) → (01) с помощью изоморфного детерминированного конечного автомата (ДКА) K(S, A1 ) со входным алфавитом A1 = {00, 01, 10}, обозначив буквой 00 сигнал освобождения канала 1 (в том числе «холостой ход» при простое (01) этого канала), буквой 01 — сигнал освобождения канала 2 (в том числе «холостой ход» при простое (10) этого канала), буквой 10 — сигнал прихода входной заявки. Отношение вероятностей появления букв 00 и 01 во входном потоке сигналов ДКА K(S, A1 ) равно q1 /q2 . Соответствующим образом заменим матрицу и граф переходов ДКА Рис. 2. Граф переходов ДКА K(S, A1 ) K(S, A1 ) (см. табл. 3 и рис. 2). Отметим отсутствие повторов входных сигналов в разметке дуг, выходящих из одной вершины ДКА K(S, A1 ), в отличие от случая НКА K(S, A) (ср. рис. 1). Тогда рекурсивную (то есть разрешимую последовательно) систему линейных рекурсивных нестохастических уравнений состояний автомата K(S, A1 ) получим из соответствующей таблицы истинности при входном сигнале a1 (n)a2 (n) = a1 a2 ∈ A1 : Матрица переходов ДКА S\A1 00 01 (00) (00) (00) (01) 01) (00) (10) (00) (10) (11) (01) (10) s1 (n + 1) = a1 ⊕ a1 a2 ⊕ a2 s1 ⊕ a1 a2 s1 = αn ⊕ βn s1 (n), s2 (n + 1) = a1 s1 ⊕ a1 a2 s1 ⊕ a2 s2 ⊕ s2 ⊕ a1 a2 s1 s2 = γn ⊕ δn s2 (n), (4) (5) где αn := a1 a2 , βn := a1 a2 , γn := a1 a2 s1 , δn := a2 ⊕ a1 a2 s1 . Рекурсивность системы (4), (5) проявляется в зависимости параметров уравнения (5) от решения уравнения (4). Из (4) и (5) получим явный вид уравнений состояний: δn−τ . δn−τ ⊕ s2 (0) γn−t τ =0 t=0 (6) (7) τ =0 n τ =0 t−1 t=0 n βn−τ , βn−τ ⊕ s1 (0) αn−t s2 (n + 1) = n t−1 n s1 (n + 1) = τ =0 Здесь для универсальности обозначений предполагается равенство −1 βn−τ := 1. τ =0 Поскольку n=0 βn−τ = 0, если ∃k ∈ 0, n : βk = a1 (k)a2 (k) = 0; n=0 δn−τ = τ τ = 0, если ∃k ∈ 0, n : δk = a2 (k) ⊕ a1 (k)a2 (k)s1 (k) = 0, то явные уравнения 118 Сиситема массового обслуживания с различимыми каналами как конечный автомат состояний (6) и (7) примут окончательный вид: n  α  n−t ⊕ s1 (0) ← ∀k ∈ 0, n ⇒ βk = a1 a2 = 1 ,  t=0 s1 (n + 1) = m−1   αn−t ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ βk = a1 a2 = 1 ∧ (βm = 0);  t=0 n  γ  ⊕ s2 (0) ← ∀k ∈ 0, n ⇒ δk = a2 ⊕ a1 a2 s1 = 1 ,  t=0 n−t  s2 (n + 1) = m−1   t=0 γn−t ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ δk = 1 ∧    ∧ (δm = a2 ⊕ a1 a2 s1 = 0) . Из (4) следует необходимое, но не достаточное условие a1 (n)s1 (n + 1) = a1 (n) ⊕ a1 (n)a2 (n) = a1 (n)a2 (n). Аналогично, из (5) получим необходимое, но не достаточное условие a2 (n)s2 (n + 1) = a2 (n)a1 (n)s1 (n)s2 (n). СМО со стохастической диспетчеризацией входных заявок и выработкой сигналов на освобождение приборов. В общем случае стохастического поведения пропускной способности дуг, выходящих из вершин (00) и (11), уравнения перехода зависят от совместного распределения вероятностей переходов по этим четырём дугам. Из табл. 2 получим рекурсивные стохастические булевы функции в правых частях уравнений состояний НКА s1 (n + 1) = a ⊕ s1 s2 ⊕ as1 s2 a s1 s2 ⊕ as1 ⊕ as2 as1 ⊕ as2 ⊕ as1 s2 , q 1 p1 q 2 p1 q 1 p2 q 2 p2 s2 (n + 1) = a ⊕ as1 ⊕ as1 s2 a ⊕ s1 s2 ⊕ as1 a a ⊕ s1 s2 ⊕ as1 s2 . q 1 p1 q 2 p1 q 1 p2 q 2 p2 Следует заметить, что произведение qi pj не означает вероятность одновременного появления двух сигналов 0 и 1, а лишь исчисляет вероятность, что в данный момент времени при поступлении сигнала 1 заявка отправилась бы на j-тый прибор, а при поступлении сигнала 0 сработал бы i-тый прибор. Построим изоморфный ДКА K(S, A2 ) со входным алфавитом A1 = {00, 01, 10, 11}, обозначив буквой 00 сигнал освобождения канала 1 (в том числе «холостой ход» при простое (01) этого канала), буквой 01 — сигнал освобождения канала 2 (в том числе «холостой ход» при простое (10) этого канала), буквой 10 — сигнал прихода входной заявки, которую может обработать только канал 1, буквой 11 — сигнал прихода входной заявки, которую может обработать только канал 2. Отношение вероятностей появления букв 00 и 01 во входном потоке сигналов ДКА K(S, A2 ) равно q1 /q2 , а отношение вероятностей появления букв 10 и 11 во входном потоке сигналов равно p1 /p2 . Соответствующим образом заменим граф переходов (см. рис. 3). Петли на орграфе вновь являются детерминированными, и переход по ним осуществляется при поступлении подходящего входного сигнала (ср. рис. 1). 119 К о т е н к о А. П., Б у к а р е н к о М. Б. Рис. 3. Граф переходов ДКА K(S, A2 ) Тогда уравнения состояний автомата K(S, A2 ) получим из соответствующей таблицы истинности при входной букве a1 (n)a2 (n) = a1 a2 ∈ A2 . Аналогично первому случаю составим таблицу истинности детерминированных булевых функций s1 (n + 1) и s2 (n + 1) ДКА K(S, A2 ) и выведем из их СДНФ линейные независимые рекурсивные детерминированные уравнения состояний s1 (n + 1) = a1 ⊕ a1 a2 ⊕ a2 s1 = α(n) ⊕ β(n)s1 (n), s2 (n + 1) = s2 ⊕ a2 s2 ⊕ a1 a2 = γ(n) ⊕ δ(n)s2 (n), def def def (8) (9) def где α(n) = a1 a2 , β(n) = a2 , γ(n) a 1 a2 , δ(n) = a2 . Из (8) и (9) окончательно получим явный вид уравнений состояний (6) и (7): n  α(n − t) ⊕ s (0) ← ∀k ∈ 0, n ⇒ β(k) = a (k) = 1 ,  1 2  t=0  m−1 s1 (n + 1) =   t=0 α(n − t) ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ β(k) = a2 (k) = 1 ∧    ∧(β(m) = a2 (m) = 0); n  γ(n − t) ⊕ s (0) ← ∀k ∈ 0, n ⇒ δ(k) = a (k) = 1 ,  2 2  t=0  s2 (n + 1) = m−1   t=0 γ(n − t) ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ δ(k) = a2 (k) = 1 ∧    ∧ (δ(m) = a2 (m) = 0) . Из (8) следует необходимое, но не достаточное линейное условие a2 (n)s1 (n + 1) = a2 (n)s1 (n), эквивалентное утверждению a2 (n) = 1 ⇒ s1 (n + 1) = s1 (n), которое легко усмотреть из сравнения соответствующих столбцов и строк таблицы истинности. Аналогично, из (9) получим необходимое, но не достаточное линейное условие a2 (n)s2 (n + 1) = a2 (n)a1 (n), эквивалентное утверждению a2 (n) = 1 ⇒ s2 (n + 1) = a1 (n), которое также легко усмотреть из сравнения соответствующих столбцов и строк таблицы истинности. 120 Сиситема массового обслуживания с различимыми каналами как конечный автомат СМО со стохастической диспетчеризацией и детерминированной выработкой сигналов на освобождение приборов. При недетерминированной диспетчеризации входных заявок с вероятностью p1 < 1 перехода по оптимальной дуге (00) → (01) и вероятностью p2 = 1 − p1 > 0 перехода по неоптимальной дуге (00) → (01) введём детерминированную диспетчеризацию выходных заявок: q1 = 1, Таблица 4 q2 = 0. Матрица переходов НКА K(S,A) да- Матрица переходов НКА K(S, A) с двумя стохастина в табл. 4. Из таблицы истинности стохастических ческими дугами (00) → (10) и (00) → (01) булевых функций s1 (n + 1) и s2 (n + 1) НКА 0 1 K(S, A) с двумя стохастическими дугами (10) (01) (00) → (10) и (00) → (01) получим нели(00) (00) p1 p2 нейные нестационарные рекурсивные стоха(01) (00) (11) стические булевы функции в правой части (10) (00) (11) уравнений состояний НКА K(S, A) с двумя (11) (10) (11) оставшимися недетерминированными переходами (00) → (10) и (00) → (01): s1 (n + 1) = a ⊕ s1 s2 ⊕ as1 s2 as1 ⊕ as2 ⊕ s1 s2 , p1 p2 (10) s2 (n + 1) = as1 ⊕ as2 ⊕ as1 s2 a . p1 p2 (11) Из (10) следуют линейные детерминированные нестационарные необходимые, но не достаточные условия a(n)s1 (n)s1 (n + 1) = a(n)s1 (n) a(n)s1 (n) = a(n)s1 (n), p1 p2 a(n)s2 (n)s1 (n + 1) = a(n)s2 (n) a(n)s2 (n) = a(n)s2 (n), p1 p2 эквивалентные утверждению (a(n)s1 (n) = 1)∨(a(n)s2 (n) = 1) ⇒ s1 (n+1) = 1, которое можно также усмотреть из сравнения соответствующих столбцов и строк таблицы истинности. Аналогично, из (11) получим линейное детерминированное нестационарное необходимое, но не достаточное условие s1 (n)s2 (n + 1) = a(n)s1 (n) a(n)s1 (n) = s1 (n)a(n), p1 p2 эквивалентное утверждению s1 (n) = 1 ⇒ s2 (n + 1) = a(n). Это равенство также легко усмотреть из сравнения соответствующих столбцов и строк таблицы истинности. Избавимся от стохастичности дуг (00) → (10) и (00) → (01) с помощью изоморфного ДКА K(S, A3 ) со входным алфавитом A3 = {00,10,11}, обозначив буквой 00 сигнал выхода обработанной заявки (в том числе «холостой 121 К о т е н к о А. П., Б у к а р е н к о М. Б. Таблица 5 ход» при простое (00) системы), буквой Матрица переходов ДКА K(S, A3 ) 10 — сигнал прихода входной заявки, которую может обслужить только канал 2 (в том числе отказ (01) при занято(00) сти этого канала или общий отказ (11) (01) всей СМО), буквой 11 — сигнал прихо(10) да входной заявки, которую может об(11) служить только канал 1 (в том числе отказ (10) при занятости этого канала или общий отказ (11) всей СМО). Отношение вероятностей появления букв 11 и 10 во входном потоке сигналов ДКА K(S, A3 ) равно p1 /p2 при условии p1 + + p2 = 1. Соответствующим образом заменим матрицу и граф переходов ДКА K(S, A3 ) (см. табл. 5 и рис. 4). Отметим отсутствие повторов входРис. 4. Граф переходов ДКА K(S, A3 ) ных сигналов в разметке дуг, выходящих из одной вершины ДКА K(S, A3 ), в отличие от случая НКА K(S, A) (ср. рис. 4). Тогда уравнения состояний автомата K(S, A3 ) получим из таблицы истинности детерминированных булевых функций s1 (n + 1) и s2 (n + 1) при входном сигнале a1 (n)a2 (n) = a1 a2 ∈ A3 : 00 (00) (00) (00) (10) 10 (01) (01) (11) (11) 11 (10) (11) (10) (11) s1 (n + 1) = a1 a2 ⊕ a1 s1 ⊕ a1 a2 s1 ⊕ s1 s2 ⊕ a1 s1 s2 ⊕ a2 s1 s2 ⊕ a1 a2 s1 s2 = = α(n) ⊕ β(n)s1 (n), (12) (13) s2 (n + 1) = a1 ⊕ a1 a2 ⊕ a1 a2 s2 = γ(n) ⊕ δ(n)s2 (n), def def def где α(n) = a1 (n)a2 (n), β(n) = a2 (n) a1 (n) ⊕ a1 (n)s2 (n) , γ(n) = a1 (n)a2 (n), def δ(n) = a1 (n)a2 (n). Из (12) и (13) окончательно получим явный вид уравнений состояний n  α(n − t) ⊕ s (0) ←  1  t=0   ∀k ∈ 0, n ⇒ β(k) = a2 (k) a1 (k) ⊕ a1 (k)s2 (k) = 1 , s1 (n + 1)= m−1     α(n − t) ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ β(k) = 1 ∧ (β(m) = 0) ;  t=0 n  γ(n − t) ⊕ s (0) ← ∀k ∈ 0, n ⇒ δ(k) = a (k)a (k) = 1 ,  2 1 2  s2 (n + 1)= t=0 m−1   γ(n − t) ← (m n) ∧ ∀k ∈ 0, m − 1 ⇒ δ(k) = 1 ∧ (δ(m) = 0) .  t=0 Из (12) следует необходимое, но не достаточное линейное условие a1 (n)a2 (n)s1 (n + 1) = a1 (n)a2 (n), 122 Сиситема массового обслуживания с различимыми каналами как конечный автомат эквивалентное утверждению a1 (n)a2 (n) = 1 ⇒ s1 (n + 1) = 1, которое легко усмотреть из сравнения соответствующих строк и столбцов таблицы истинности. Аналогично, из (13) также получим необходимое, но не достаточное линейное условие s2 (n)s2 (n + 1) = s2 (n)a1 (n), эквивалентное утверждению s2 (n) = 1 ⇒ s2 (n + 1) = a1 (n), которое легко усмотреть из соответствующей таблицы истинности. Заключение. Выкладки аналогично переносятся на случай большего числа каналов обслуживания, наличия очередей, а также совместного стохастического поведения параметров каналов обслуживания. Несмотря на значительное усложнение неклассического орграфа СМО, явный вид уравнений переходов состояний позволяет проводить имитационное моделирование в случае как простейших, так и произвольных случайных процессов поступления и обработки заявок. Рост ёмкости очереди приводит к увеличению r-значности поставленной задачи, которая легко может быть снижена до r = 2 (подобно рассматриваемому случаю) за счёт увеличения длины вектора Si , описывающего i-тое состояние СМО в разработанной авторами нотификации. Отметим, что такие среды автоматизированного динамического моделирования систем, как GPSS (включая GPSS World) и Simulink, не располагают удовлетворительным инструментарием моделирования описанных в работе СМО, в частности, они не позволяют учитывать предложенную авторами диспетчеризацию поступающих заявок. Разработанные авторами нотификация состояний и алгоритм получения уравнений состояния подобных систем позволяют: 1) при необходимости распространить его на другие типы протоколов диспетчеризации; 2) автоматизировать процесс получения уравнений состояний; 3) моделировать описанные СМО практически в любой программной среде, допускающей работу с булевой алгеброй. На основе разработанной нотификации, в частности, авторами был создан комплекс программ, полностью автоматизирующий построение, разметку и визуализацию графа состояний подобных СМО для произвольного числа каналов и мест в очередях к ним.

About the authors

Andrey P Kotenko

Samara State Technical University

Email: ako1959@mail.ru
(Ph. D. (Phys. & Math.)), Associate Professor, Dept. of Applied Mathematics & Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russia

Maksim B Bukarenko

Samara State Technical University

Email: maxim.bukarenko@gmail.com
Postgraduate Student, Dept. of of Applied Mathematics & Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russia

References

Supplementary files