Моделирование конечными автоматами систем массового обслуживания с различимыми каналами
Автор: Котенко Андрей Петрович, Букаренко Максим Борисович
Журнал: Известия Самарского научного центра Российской академии наук @izvestiya-ssc
Рубрика: Автоматизированные системы научных исследований
Статья в выпуске: 4-2 т.16, 2014 года.
Бесплатный доступ
Изложена постановка задачи исследования систем массового обслуживания с различимыми каналами, обладающими различной пропускной способностью и/или отдельными очередями. В этом случае нельзя применить результаты классической теории массового обслуживания с линейным графом состояний процесса “гибели и размножения”. Предложено описание системы с различимыми каналами конечными детерминированными и недетерминированными автоматами. Это позволило провести имитационное моделирование поведения системы при различных вариантах диспетчеризации входных заявок.
Система массового обслуживания, неоднородные каналы обслуживания, раздельные очереди каналов обслуживания, конечные автоматы
Короткий адрес: https://sciup.org/148203201
IDR: 148203201 | УДК: 519.248
Modeling systems finite automata queuing visible channels
Distinct channels queuing systems with servers of different processing capacities and separate queues are considered. In this case the results of classical queuing theory, which suppose that a state graph is a linear “birth and death” process, graph. System with distinct channels is suggested to be described by deterministic and stochastic finite automatons. This approach gives an opportunity to carry out simulation of the system behavior under different variants of entries scheduling.
Текст научной статьи Моделирование конечными автоматами систем массового обслуживания с различимыми каналами
внутренних состояний S ={(00),(01),(10),(11)} без выделенных начального и конечного состояний, входным алфавитом A ={0,1} и пустым выходным алфавитом. Буква 1 входного алфавита A соответствует приходу заявки в систему, а 0 – выработке сигнала освобождения заявки одним из каналов.
Рассмотрим все сочетания стохастической природы дуг орграфа, представленные (не)де-терминированными конечными автоматами.
При детерминированной диспетчеризации входных заявок получим для a = a ( n ), s 1= s 1( n ), s 2= s 2( n ) нелинейные нестационарные рекурсивные стохастические булевы функции в правой части уравнений состояний НКА K ( S , A ):
5 1 ( n + 1 ) =
5 2 ( n + 1 ) =
а Ф 5 1 5 2 Ф as 1 5 2
q 1
a q2
a Ф a5 1 Ф a5 1 5 2
q 1
a Ф 5 1 5 2 Ф a5 1 q 2
Тогда рекурсивную (то есть разрешимую последовательно) систему линейных рекурсивных нестохастических уравнений состояний автомата K ( S , A 1) получим из соответствующей таблицы истинности при входном сигнале a ( n a ( n ) = aa 2 е A 1 :
5 1 ( n +1) = a 1 Ф a 1 a 2 Ф a 2 5 1 Ф a 1 a 2 5 1 =
= « Ф Л51(n),
5 2 ( n +1) = a 1 5 1 Ф a 1 a 2 5 1 Ф a 2 5 2 Ф 5 2 Ф a 1 a 2 5 1 5 2 =
= Yn Ф 5_n52 (n),_ _ где an := a a 2, Pn := a a2, Yn := a1a2 5i, 5n := a2 Фс^с^5.
Отсюда получим явный вид уравнений состояний
n t-1 n s 1 (n + 1)= I « -t П Pn-. ® s 1 (° )П A t=° T=° T= °
|
s 2 ( n + 1 ) = |
a © as 1 © as 1 s 2 |
a © s 1 s 2 © as 1 |
a |
a © s 1 s 2 © as 1 s 2 |
|
q 1 P 1 |
q 2 P 1 |
qP 2 |
q 2 p 2 |
nt-1 n s2 (n + 1) = I Yn-t П 5n-t ® s2 (0 )П 5n-t .
t = ° T = ° T = °
Здесь для универсальности обозначений по-
лагается равенство
- 1
П P n -T : = 1 .
T = °
Поскольку,
П = o P n -T = ° , если 3 k G °’ n • P k = a 1 ( kV 2 ( k ) = ° ;
П Т = ° ^ n -T = ° , если 3 k G °, n : 8 k = a 2 ( k ) © a ( k ) a 2 ( k Ы k ) = °,
то явные уравнения состояний примут окончательный вид:
n
I « n - 1 © s 1 ( ° ) <
t = °
<
s 1 ( n + 1 ) =
( v k g °, n ^ P k
= a 1 a 2 = 1
s 2 ( n + 1 ) =
<
m - 1
I « n - t <
< (m < nЫд = °)л л (vk g °, m -1 ^ Pk = a1 a2 = 1)
Построим изоморфный ДКА K ( S , A 2) со входным алфавитом A 1={00,01,10,11}, обозначив буквой 00 сигнал освобождения канала 1 (в том числе “холостой ход” при простое (01) этого канала), буквой 01 – сигнал освобождения канала 2 (в том числе “холостой ход” при простое (10) этого канала), буквой 10 – сигнал прихода входной заявки, которую может обработать только канал 1, буквой 11 – сигнал прихода входной заявки, которую может обработать только канал 2. Отношение вероятностей появления букв 00 и 01 во входном потоке сигналов ДКА K ( S , A 2) равно q 1 ] q 2 , а отношение вероятностей появления букв 10 и 11 во входном потоке сигналов равно pjр 2 .
Аналогично первому случаю, составим таблицу истинности детерминированных булевых функций s 1( n +1) и s 2( n +1) ДКА K ( S , A 2) и выведем из их СДНФ линейные независимые рекурсивные детерминированные уравнения состояний S 1 ( n + 1) = a © aa 2 © a 2 s 1 = « ( n ) © P ( n ) s 1 ( n ) , s 2 ( n + 1) = s 2 © a 2 s 2 © a 1 a 2 = / ( n ) © J ( n ) s 2 ( n ) , где « ( n ) : = a 1 a 2 , P ( n ) : = a 2 , y ( n ) : = a 1 a 2 ,
^ ( n ) : = a 2 .
Отсюда получим явный вид уравнений состояний:
n lYn-1 © s2 (°)< t=° ,
k
= a 2 © a 1 a 2 s 1 = 1
m - 1
l Y n - 1 < t = °
s 1 ( n + 1 ) = <
л ( v k g °, m - 1 ^ л fe = a 2 © a 1 a 2 s 1
4 = 1 ) л = ° )
I«(n -1)©s(°)< t=°
< ( v k g °, n ^ P ( k ) = a 2
m - 1
I«(n -1)< t=°
л ( v к g °, m - 1 ^ P ( k ) = a 2 ( k ) = 1 ) л л ( p ( m ) = a 2 ( m ) = ° ) ;
СМО со стохастической диспетчеризацией входных заявок и выработкой сигналов на освобождение приборов . В общем случае стохастического поведения пропускной способности дуг, выходящих из вершин (00) и (11), уравнения перехода зависят от совместного распределения вероятностей переходов по этим четырём дугам. В этом случае получим рекурсивные стохастические булевы функции в правых частях уравнений состояний НКА
|
s 1 ( n + 1 ) = |
a © s 1 s 2 © ass 2 |
a |
s 1 s 2 © as 1 © as 2 |
as 1 © as 2 © as 1 s 2 |
|
Q 1 P 1 |
Q 2 P 1 |
Q 1 P 2 |
q 2 P 2 |
n
IY(n- t )© s 2 M< s 2 (n + 1) = <
< ( v k g °, n ^ ^ ( k ) = a 2 ( k ) = 1 ), I Y ( n - t )<
< ( m < n ) л
л ( v k g °, m - 1 ^ ^ ( k ) = a 2 ( k ) = 1 ) л л ( ^ ( m ) = a 2 ( m ) = ° )
СМО со стохастической диспетчеризацией и детерминированной выработкой сигналов на освобождение приборов. При недетерминированной диспетчеризации входных заявок с вероятностью p 1<1 перехода по оптимальной дуге (00)>(10) и вероятностью p 2=1– p 1>0 перехода по неоптимальной дуге (00)>(01) введём детерминированную диспетчеризацию выходных заявок: q 1=1, q 2=0.
Из таблицы истинности стохастических булевых функций s 1( n +1) и s 2( n +1) НКА K ( S , A ) с двумя стохастическими дугами (00) ^ (10) и (00) ^ (01) получим нелинейные нестационарные рекурсивные стохастические булевы функции в правой части уравнений состояний НКА K ( S , A ) с двумя оставшимися недетерминированными переходами (00) ^ (10) и (00) ^ (01):
а5 1 Ф а5 2 Ф 5 1 5 2 p 2
а Ф 5 1 5 2 Ф а5 1 5 2
5 1 ( П + 1 ) =
P i
5 2 ( n + 1 ) =
|
а5 1 Ф а5 2 Ф а5 1 5 2 |
a |
|
P 1 |
P 2 |
Тогда уравнения состояний автомата K ( S , A 3) получим из таблицы истинности детерминированных булевых функций s 1( n +1) и s 2( n +1) при входном сигнале а 1 ( n ) а 2 ( n ) = а 1 а 2 Е A 3 :
5 1 ( n + 1) = = aa2 Ф а 1 5 1 Ф а 1 а 2 5 1 Ф 5 1 5 2 Ф
Ф a 5 1 s 2 Ф а 2 5 1 5 2 Ф а 1 а 2 5 1 5 2 = « ( n ) Ф ^ ( n ) 5 1 ( n ) , 5 2 ( n + 1) = а Ф а а 2 Ф а а 2 5 2 = / ( n ) Ф J ( n ) 5 2 ( n ) , где а ( n ) : = а 1 ( n ) а 2 ( n ) ,
l ( n ) : = а 2 ( n ) [ а 1 ( n ) Ф а 1 ( n 5 2 ( n ) ] ,
у ( n ) : = а 1 ( n ) а 2 ( n ) , ^ ( n ) : = а 1 ( n ) а 2 ( n ) .
Таким образом, получим явный вид уравнений состояний
n
^ а ( n - 1 ) Ф 5 1 ( 0 ) ^
5 1 ( n + 1 ) = <
^ ( v k е 0, n ^
^ ^ ( к ) = а 2 ( к ) [ а 1 ( к ) Ф а 1 ( k ) 5 2 ( к ) ] = 1 ),
^ о ( n - 1 ) ^
t = 0
^ ( m < n ) л
a ( v к е 0, m - 1 ^ ^ ( к ) = 1 ) л
л(^( m ) = 0);
5 2 ( n + 1 ) = "
jh r( n- t)Ф 5 2 (o)< t=0 , ______ X
< ( v к е 0, n ^ £ ( к ) = а 1 ( к ) а 2 ( к ) = 1 ), m - 1
Zr( n -1 )< t=0
<( m < n )a
a ( v к е 0, m - 1 ^ ^ ( к ) = 1 ) л
_л(^( m ) = 0).
Заключение . Выкладки аналогично переносятся на случай большего числа каналов обслуживания, наличия очередей, а также совместного стохастического поведения параметров каналов обслуживания. Несмотря на значительное усложнение неклассического орграфа СМО явный вид уравнений переходов состояний позволяет проводить имитационное моделирование как в случае простейших, так и произвольных случайных процессов поступления и обработки заявок.
Список литературы Моделирование конечными автоматами систем массового обслуживания с различимыми каналами
- Котенко А.П. Аналитическое описание систем массового обслуживания с использованием колец вычетов [Текст]/А.П. Котенко, М.Б. Букаренко//Труды VII Всероссийской научной конференции “Математическое моделирование и краевые задачи”. -Самара: Изд-во СамГТУ, 2010. -С. 136-140.
- Букаренко М.Б. Система массового обслуживания с раздельными очередями к каналам [Текст]/М.Б. Букаренко//Тезисы 42-й Всероссийской конференции “Современные проблемы математики”. -Екатеринбург: Институт математики и механики УрО РАН, 2011. -С. 11-13.
- Комарова Е.Д. Исследование транспортной задачи линейного программирования как системы массового обслуживания [Текст]/Е.Д. Комарова, А.П. Котенко//Материалы VI Международной научно-практической конференции “Научная дискуссия: вопросы технических наук”. -М.: Изд-во “Международный центр науки и образования”, 2013. -С. 17-22.
- Котенко А.П. Комплекс программ имитационного моделирования работы системы массового обслуживания с неоднородными приборами и раздельными накопителями [Текст]/А.П. Котенко, М.Б. Букаренко//Вестник СамГТУ. Серия “Физ.-мат. науки”, №2 (31). -Самара: Изд-во СамГТУ, 2013. -С. 50-57.
- Котенко А.П. Система массового обслуживания с различимыми каналами как конечный автомат [Текст]/А.П. Котенко, М.Б. Букаренко//Вестник СамГТУ. Серия “Физ.-мат. науки”, №3 (28). -Самара: Изд-во СамГТУ, 2012. -С. 114-124.
- Котенко А.П. Математическое моделирование систем массового обслуживания с использованием колец вычетов в управлении организационно-экономическими системами [Текст]/А.П. Котенко, М.Б. Букаренко//“Управление организационно-экономическими системами”, вып. 7. -Самара: Изд-во СГАУ, 2010. -С. 31-34.
