A queuing system with distinct devices as the finite state machine

Abstract


Queuing systems with distinct channels are considered. Channels may have different capacities (from each other) and distinct queues. The term “dispatch control” is introduced to optimize the system, considering the average time of service and failure probability minimization. These systems are treated as deterministic or nondeterministic finite state machines. State equations of these systems in the form of Zhegalkin polynomial are derived.

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
244, Molodogvardeyskaya st., Samara, 443100, Russia
(Ph. D. (Phys. & Math.)), Associate Professor, Dept. of Applied Mathematics & Computer Science

Maksim B Bukarenko

Samara State Technical University

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

References

  1. Артамонов Г. Т, Брехов О. М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978. 368 с. [Artamanov G. T., Brehov O. M. Analytic probability ´ models of the functioning of computers. Moscow: Energiya, 1978. 368 pp.]
  2. Введенская Н. Д., Добрушин Р. Л., Карпелевич Ф. И. Система обслуживания с выбором наименьшей из двух очередей – асимптотический подход // Пробл. передачи информ., 1996. Т. 32, № 1. С. 20–34.
  3. Введенская Н. Д. Большая система обслуживания с передачей сообщения по нескольким путям // Пробл. передачи информ., 1998. Т. 34, № 2. С. 98–108.
  4. Печинкин А. В., Таташев А. Г. Обобщение дисциплины преимущественного разделения процессора // Изв. АН СССР. Техн. кибернетика, 1981. № 4. С. 120–125.
  5. Д’Апиче Ч., Манзо Р., Печинкин А. В. Система обслуживания MAPK /GK /1 конечной емкости с обобщенной дисциплиной преимущественного разделения прибора // Автомат. и телемех., 2004. № 11. С. 114–121.
  6. Rykov V. V. Monotone Control of Queueing Systems with Heterogeneous Servers // Queueing Syst., 2001. Vol. 37, no. 4. Pp. 391–403.
  7. de V´ricourt F., Zhou Y.-P. On the incomplete results for the heterogeneous server e problem // Queueing Syst., 2006. Vol. 52, no. 3. Pp. 189–191.
  8. Nawijn W. M. On a two-server finite queuing system with ordered entry and deterministic arrivals // Eur. J. Oper. Res., 1984. Vol. 18, no. 3. Pp. 388–395.
  9. Elsayed E. A. Multichannel queueing systems with ordered entry and finite source // Comput. Oper. Res., 1983. Vol. 10, no. 3. Pp. 213–222.
  10. Котенко А. П., Букаренко М. Б. Аналитическое описание систем массового обслуживания с использованием колец вычетов / В сб.: Труды седьмой Всероссийской научной конференции с международным участием. Часть 2 / Математическое моделирование и краевые задачи. Самара: СамГТУ, 2010. С. 136–140.
  11. Букаренко М. Б. Система массового обслуживания с раздельными очередями к каналам / В сб.: Современные проблемы математики: Тезисы 42-ой Всероссийской конференции. Екатеринбург: ИММ УрО РАН, 2011. С. 11–13.

Statistics

Views

Abstract - 17

PDF (Russian) - 2

Cited-By


Refbacks

  • There are currently no refbacks.

Copyright (c) 2012 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies