Моделирование конечными автоматами систем массового обслуживания с различимыми каналами

Автор: Котенко Андрей Петрович, Букаренко Максим Борисович

Журнал: Известия Самарского научного центра Российской академии наук @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.
Еще
Статья научная