Моделирование конечными автоматами систем массового обслуживания с различимыми каналами
Автор: Котенко Андрей Петрович, Букаренко Максим Борисович
Журнал: Известия Самарского научного центра Российской академии наук @izvestiya-ssc
Рубрика: Автоматизированные системы научных исследований
Статья в выпуске: 4-2 т.16, 2014 года.
Бесплатный доступ
Изложена постановка задачи исследования систем массового обслуживания с различимыми каналами, обладающими различной пропускной способностью и/или отдельными очередями. В этом случае нельзя применить результаты классической теории массового обслуживания с линейным графом состояний процесса “гибели и размножения”. Предложено описание системы с различимыми каналами конечными детерминированными и недетерминированными автоматами. Это позволило провести имитационное моделирование поведения системы при различных вариантах диспетчеризации входных заявок.
Система массового обслуживания, неоднородные каналы обслуживания, раздельные очереди каналов обслуживания, конечные автоматы
Короткий адрес: https://sciup.org/148203201
IDR: 148203201
Текст научной статьи Моделирование конечными автоматами систем массового обслуживания с различимыми каналами
внутренних состояний 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.