Исследование системы управления конфликтными потоками в классе алгоритмов с дообслуживанием

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Дипломная работа

Исследование системы управления конфликтными потоками в классе алгоритмов с дообслуживанием



Введение

управление алгоритм имитационный математический

Во многих областях жизнедеятельности человека важную роль играют системы массового обслуживания (СМО), то есть такие системы, в которых с одной стороны возникают массовые запросы (требования, заявки) на выполнение каких-либо услуг, а с другой стороны происходит удовлетворение этих запросов. Примеров СМО множество: магазины, банки, больницы, порты, склады, телефонные станции, билетные кассы, ремонтные мастерские, конвейерные линии и многое другое. Часто возникают ситуации, когда СМО не успевают одновременно обслуживать все поступающие заявки. Если у заявок имеется возможность встать в очередь, такие системы называются СМО с ожиданием [1].

Теория массового обслуживания - это раздел теории вероятностей, представляющий собой основы эффективного конструирования и эксплуатации СМО.

Актуальной задачей теории массового обслуживания в классе СМО с ожиданием является исследование систем алгоритмического управления конфликтными потоками. Широкое применение данное направление нашло в транспортных задачах.

Работа посвящена изучению системы управления конфликтными потоками в классе алгоритмов с дообслуживанием. Состоит из введения, двух глав, заключения и приложения.

Введение содержит краткую характеристику работы.

Первая глава посвящена анализу системы управления конфликтными потоками Бартлетта в классе алгоритмов с дообслуживанием. Дано описание рассматриваемой системы на содержательном уровне. Система представлена как система массового обслуживания с переменной структурой, приведено математическое описание всех ее исходных элементов, изучены некоторые вероятностные свойства процесса управления.

Во второй главе с целью построения имитационной модели и оптимизации изучаемой системы управления конфликтными потоками была разработана программа. Программа позволяет найти минимальную статистическую оценку среднего времени пребывания произвольной заявки в системе, а также оптимальные параметры управляющего алгоритма, соответствующие этой оценке. Программа реализована на языке программирования C++. Проведено сравнение циклического алгоритма и алгоритма с дообслуживанием.

В заключении кратко сформулированы основные результаты, полученные в работе.

В приложении приведены блок-схемы, распечатка текста программы и некоторые численные результаты.



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

1.1 Описание работы системы на содержательном уровне

Рассмотрим СМО с ожиданием. В систему поступают два конфликтных однородных потока пачек и . Обслуживание этих потоков невозможно вести в одни и те же временные интервалы. Аналогом такой СМО в реальной жизни является регулируемый четырехсторонний автомобильный перекресток с установленным на нем автоматом-светофором. Конфликтные входные потоки пачек и - это приходящие на перекресток автоколонны, а обслуживающее устройство (ОУ) - это светофор.

Для управления конфликтными потоками в ОУ используется алгоритм с дообслуживанием. У светофора имеется 6 режимов работы: , где

- режим работы основного зеленого света в направлении потока , переезд через перекресток разрешен только автомобилям потока ;

- режим работы основного зеленого света в направлении потока, переезд через перекресток разрешен только автомобилям потока ;

, - режимы работы желтого света в направлении обоих потоков. В этих режимах потоки не обслуживаются, система осуществляет ориентации, переналадки, разогрев;

- режим дополнительного зеленого света в направлении потока ;

- режим дополнительного зеленого света в направлении потока .

Смена режимов ОУ происходит в некоторые специальные моменты времени , .

Схематично система представлена на рисунке 1.



Рисунок 1. Рассматриваемая СМО с ожиданием

управление алгоритм имитационный математический

Опишем процесс переключения режимов ОУ. Пусть в начальный момент времени светофор переключился в режим желтого света . В следующий момент времени светофор переключается в режим основного зеленого света в направлении потока . Если к моменту окончания этого режима в направлении потока имеется очередь, то в следующий момент времени светофор переключается в режим дополнительного зеленого света в направлении потока . Если после работы режима в направлении потока очереди нет, то светофор переключается в режим желтого света . Если светофор переключился в режим , то после его окончания он также переключается в режим желтого света . В следующий момент времени светофор переключается в режим основного зеленого света в направлении потока . Если к моменту окончания этого режима в направлении потока имеется очередь, то в следующий момент времени светофор переключается в режим дополнительного зеленого света в направлении потока , иначе - в режим желтого света . Если светофор переключился в режим , то после его окончания он также переключается в режим желтого света . Впоследствии переключение режимов светофора будет происходить по описанной выше схеме.

Таким образом, процесс переключения режимов ОУ зависит от очередей по каждому из потоков, и рассматриваемая система является системой с обратной связью. Схематично граф переключения режимов ОУ представлен на рисунке 2.

Рисунок 2. Граф переключения режимов ОУ

Перейдем к построению математической модели рассматриваемой системы.

1.2 Представление системы управления конфликтными потоками как системы массового обслуживания с переменной структурой

К особенностям изучаемой системы относится следующее:

- входные потоки имеют структуру в виде пачек, интервалы между поступающими требованиями имеют сложную статистическую связь;

- в системе имеются режимы, в которых потоки не обслуживаются, система осуществляет разогрев, ориентацию, переналадки;

- входные потоки являются конфликтными.

Под конфликтностью входных потоков понимается ситуация, когда обслуживание заявок конфликтных потоков возможно лишь в непересекающиеся промежутки времени.

Указанные выше особенности привели к тому, что адекватной математической моделью систем управления конфликтными потоками является СМО с переменной структурой [2].

Исходными элементами СМО с переменной структурой являются:

- входные потоки ;

- ОУ;

- потоки насыщения - выходные потоки системы при бесконечной очереди по каждому из направлений.

- стратегия механизма обслуживания , под которой понимаются правила отбора заявок из накопителей очередей.

Схематично эта система показана на рисунке 3.

В связи с тем, что изучается СМО с ожиданием, по каждому из потоков имеется бункер-накопитель объемом соответственно. Через на рисунке 3 обозначены реальные выходные потоки системы.

Рисунок 3. СМО с переменной структурой

Для того чтобы задать СМО с переменной структурой, необходимо описать все ее исходные составные элементы: входные потоки , ОУ, потоки насыщения и стратегию механизма обслуживания .

Перейдем к описанию составных элементов изучаемой СМО с переменной структурой.

Описание входного потока

Рассмотрим поток с независимым движением автомобилей. Математической моделью такого потока является поток Пуассона [1]. При плохой видимости на дорогах, при плохих погодных условиях у автомобилей исчезает возможность свободно обгонять друг друга, и поток автомобилей превращается в поток автоколонн (транспортных пачек). В этом случае вслед за медленными машинами выстраиваются быстрые, ожидающие возможности обгона. Поток транспортных пачек - это требования, которые условно могут быть объединены в группы (пачки) по принципу близости моментов их поступления в систему. Изменение погодных условий носит случайный характер, то есть транспортный поток испытывает влияние случайных факторов. Таким образом, под влиянием случайных факторов входной поток Пуассона может превратиться в поток транспортных пачек.

Схематично данная ситуация представлена на рисунке 4, где серым цветом выделены медленные автомобили.

Рисунок 4. Изменение структуры входного потока

Адекватной математической моделью для потока, имеющего структуру в виде пачек, является поток Бартлетта. Поток Бартлетта описывается нелокально, с помощью векторной случайной последовательности , где - последовательность моментов наблюдения. В качестве выбираются моменты поступления первых требований в пачке (моменты поступления медленных автомобилей). В этом случае случайная величина описывает длину пачки, поступившей в систему за й такт наблюдения по му потоку [3].

При таком выборе моментов наблюдения число заявок в каждой пачке будет иметь следующее распределение:

, (1)

где это параметры распределения числа заявок в каждой пачке в м потоке, .

Однако вышеприведенное распределение не зависит от конкретных реализаций моментов наблюдения. Выбор моментов наблюдения влияет лишь на физический смысл , поэтому распределение (1) случайных величин перепишется в виде:

(2)

Средняя длина пачки (среднее число автомобилей в пачке) равна:

(3)

Очевидно, что это вероятность поступления пачек, состоящих более чем из одной заявки, а параметр явного физического смысла не имеет, он связан с и со средней длиной пачки соотношением (3) [4].

Описание структуры обслуживающего устройства и управляющего алгоритма

Описание ОУ характеризуется описанием структуры ОУ и описанием управляющего алгоритма .

Рассмотрим структуру ОУ.

Пусть - состояние и множество состояний ОУ соответственно.

Как было отмечено выше, в изучаемой системе 6 режимов работы . Под режимом работы ОУ будем понимать такую ситуацию, когда ОУ совершает в отношении потока однотипные действия. Каждый режим дополнительно разбивается на состояний, , где - это число тактов наблюдения, которое ОУ находится в режиме . Величину можно интерпретировать как время пребывания ОУ в режиме .

Итак, {1??}, - отображение, принимающее целое положительное значение при каждом , =[2].

В реальной жизни наблюдать смену состояний ОУ можно только в том случаем, когда со сменой состояния меняется и режим работы ОУ.

Перейдем к описанию управляющего алгоритма.

Управляющий алгоритм позволяет по состоянию в заданный момент времени и по процессам поступления требований на этом такте наблюдения определить, в каком состоянии окажется ОУ в следующий момент времени.

Обозначим за состояние ОУ в момент времени , за ? очередь по потоку в момент времени , за число реально обслуженных требований потока за промежуток , - число поступивших требований в систему за промежуток . Пусть , ? ? и ?(?, ?), , , где , тогда смена состояний ОУ происходит в соответствии с рекуррентным соотношением

?, , ) (4)

Запишем алгоритм переключения состояний ОУ:

?+=

?+= (5)

?+>

?+>



Описание потоков насыщения

Для того чтобы охарактеризовать процесс обслуживания заявок в каждом потоке, вводится понятие потоков насыщения. Под потоками насыщения понимаются выходные потоки системы при бесконечных очередях по каждому из конфликтных потоков.

Потоки насыщения описываются нелокально с помощью векторной случайной последовательности , где . Здесь - максимально возможное число заявок потока , которое может быть обслужено системой за ый такт наблюдения [2].

Рассмотрим потоки насыщения специального вида, где случайная величина принимает значение из множества Случайная величина принимает значение 0, когда ОУ находится в состоянии, в котором обслуживание потока не разрешено, а - это максимальное число заявок, которое может быть обслужено, если разрешен переезд через перекресток автомобилям потока . Таким образом,

(6)

если , где - это множество состояний, в которых разрешено обслуживание заявок потока [2]. Для рассматриваемой системы множества выглядят так: .

С учетом того, что реализация случайной последовательности влияет только на физический смысл случайной величины , а значение случайной величины зависит только от текущего режима работы ОУ, то (6) запишется в следующем виде:



(7)

В силу того, что случайная величина - это максимально возможное число заявок потока , которое может быть обслужено системой за ый такт наблюдения , ее можно воспринимать как пропускную способность системы.

Математическая формализация понятий конфликтности потоков стала возможна с введением потоков насыщения и выглядит следующим образом:

(8)

Предположим, что входные потоки и потоки насыщения независимы между собой. С учетом этого предположения и формул (2), (7) получаем:

(9)

Описание стратегии механизма обслуживания

Задание входных потоков , структуры ОУ , управляющего алгоритма и потоков насыщения не определяет полностью процесс обслуживания. Для того чтобы его задать, необходимо еще описать стратегию механизма обслуживания . Для описания используется случайная величина , введенная раннее, которая обозначает число реально обслуженных требований потока за ый такт наблюдения .

В данной работе в качестве стратегии механизма обслуживания используется экстремальная стратегия [4], при которой случайная величина определяется следующим образом:

?+ (10)

Действительно, пусть , то есть на ом такте наблюдения ОУ находилось в состоянии, соответствующем обслуживанию заявок потока , тогда случайная величина определяется следующим образом:

а) если ?+, то =;

б) если ?+, то = ?+.

Пусть , то есть на ом такте наблюдения в отношении заявок потока обслуживания не проводилось, тогда == 0.

Таким образом, задано математическое описание всех исходных элементов изучаемой СМО с переменной структурой.

Процесс управления конфликтными потоками на перекрестке описывается векторной случайной последовательностью ? ?, где первая компонента задает динамику ОУ, а две другие - флуктуации длин очередей по каждому из потоков [2].

Перейдем к изучению вероятностных свойств процесса управления ? ?.

1.3 Вероятностные свойства процесса управления

Рекуррентное соотношение для процесса управления

Лемма. Рекуррентное соотношение для процесса управления ? ?

определяется равенством (11):

??=???

? (11)



Доказательство. Исходя из физического смысла очереди по потоку в момент времени , она складывается из очереди по этому потоку в момент времени с учетом того, сколько требований поступило в систему за ый такт наблюдения и за вычетом реально обслуженных системой за этот такт наблюдения заявок. Таким образом, получаем:

?? (12)

С учетом (10) формула (12) примет вид:

???+

= ? (13)

Учитывая (4), (10), (13), получаем следующее рекуррентное соотношение для процесса управления:

??=???

?

Лемма доказана.

Свойство марковости процесса управления

Теорема 1. Процесс управления ? ? является однородной марковской цепью.

Доказательство. Марковость процесса управления ? ? означает, что условное распределение вероятностей будущего состояния процесса зависит только от нынешнего состояния и не зависит от последовательности состояний, которые предшествовали нынешнему [5].

Учитывая, что выбор моментов наблюдения влияет лишь на физический смысл случайной величины , условие марковости для изучаемого процесса управления запишется так:

? ?? ?

= ? ?? ? (14)

Используя формулу полной вероятности, преобразуем левую часть равенства (14):

? ?? ?

=??

? ?

? ?

Используя равенство (9), получаем следующее:

??? ?

? ?=

? ?

??

Учитывая рекуррентное соотношение (11) для процесса управления, приходим к виду:

???

?=

???

???

=

Аналогичными преобразованиями приведем правую часть (14) к такому же виду:

? ?? ?

=??

? ?

? ?=

? ?

??=

??

? ???=

Так как левая часть равенства (14) равна его правой части, то процесс управления ? ?является марковской цепью.

С учетом (2), (6) можно сделать вывод, что вероятности вида ? ???не зависят от для всех

Таким образом, процесс управления ? ?является однородной марковской цепью. Теорема доказана.

Свойства пространства состояний процесса управления

Марковская цепь ? ?принимается значения из множества



где , а множество имеет следующий вид:

где ,

,

,

,

а - это длина очереди по му потоку к моменту переключения в режим

Теорема 2. Если то все состояния марковской цепи ?? являются несущественными, это минимальное число требований, поступающих в систему по первому потоку за один полный цикл переключений,

Доказательство. Рассмотрим произвольное состояние . За конечное число шагов из этого состояния система обязательно перейдет в состояние где .

Из (2) следует, что из состояния по цепочке переходов система с положительной вероятностью перейдет в состояние а в силу того, что то за каждый цикл переключений состояний ОУ очередь по первому потоку будет только накапливаться.

Таким образом, выйдя из состояния существует положительная вероятность в него не вернуться. Это значит, что состояние является несущественным. В силу того, что из любого состояния за конечное число шагов можно перейти в состояние то все состояния изучаемой марковской цепи ??несущественны. Лемма доказана.

Теорема 3. Если то все состояния марковской цепи ?? являются несущественными, это минимальное число требований, поступающих в систему по первому потоку за один полный цикл переключений,

Доказательство. Аналогично доказательству леммы 2.

Рекуррентные соотношения для одномерных распределений

Пусть ? ?для всех состояний .

При всех получены рекуррентные соотношения для одномерных распределений однородной марковской цепи ? ?, имеющие с учетом формул (2), (7), (10) следующий вид (при этом будем полагать сумму равной нулю, если верхний предел суммирования меньше нижнего):

где для



2. Построение имитационной модели изучаемой системы массового обслуживания

2.1 Начальные положения

Наиболее важной характеристикой работы транспортной системы является не длина очереди, как это может показаться изначально, а время пребывания произвольной заявки в системе. Это связано с тем, что в некоторых случаях длины очередей могут быть очень большими, а обслуживание заявок из этих очередей будет вестись достаточно быстро, поэтому вновь прибывающему требованию имеет смысл становиться в очередь. В других случаях очередь может быть небольшой, но обслуживание требований ведется очень долго, поэтому новому требованию разумнее отказаться от обслуживания, чем становиться в очередь. К сожалению, аналитически исследовать эту важнейшую характеристику работы транспортной системы не удается. Однако путем имитационного моделирования работы изучаемого перекрестка удается получить статистическую оценку среднего времени пребывания произвольной заявки в системе.

Примем некоторые условия. При построении имитационной модели будем рассматривать алгоритм с дообслуживанием, несколько отличающийся от того, который был рассмотрен в главе 1. Схематично изучаемый алгоритм представлен на рисунке 5.

Рисунок 5. Граф переключений режимов ОУ

Опишем процесс переключения режимов ОУ. Смена режимов ОУ происходит в некоторые специальные моменты времени , . Пусть в начальный момент времени светофор переключился в режим желтого света . В следующий момент времени светофор переключается в режим основного зеленого света в направлении потока . Если к моменту окончания этого режима в направлении потока имеется очередь, то в следующий момент времени светофор переключается в режим дополнительного зеленого света в направлении потока и остается в нем до тех пор, пока по потоку есть очередь и время ожидания заявок в очереди по потоку не превышает некоторого допустимого значения. Если после работы режима в направлении потока очереди нет, то светофор переключается в режим желтого света . Если светофор переключился в режим , то после его окончания он также переключается в режим желтого света . В следующий момент времени светофор переключается в режим основного зеленого света в направлении потока . Если к моменту окончания этого режима в направлении потока имеется очередь, то в следующий момент времени светофор переключается в режим дополнительного зеленого света в направлении потока и остается в нем до тех пор, пока по потоку есть очередь и время ожидания заявок в очереди по потоку не превышает некоторого допустимого значения, иначе светофор переключается в режим желтого света . Если светофор переключился в режим , то после его окончания он также переключается в режим желтого света . Впоследствии переключение режимов светофора будет происходить по описанной выше схеме.

Использование именно такого алгоритма продиктовано тем, что в некоторых случаях пребывание в режиме дополнительного зеленого света всего один такт времени может не дать ощутимого улучшения результата по сравнению с циклическим алгоритмом. Кроме того, аналитическое исследование данного алгоритма представляется весьма сложным.

Таким образом, при построении имитационной модели рассматривается более широкий класс алгоритмов с дообслуживанием.

2.2 Математический аппарат, используемый при построении имитационной модели

Отличием имитационной модели от математической является то, что при ее построении время измеряется не в тактах наблюдения, а в секундах. Несомненно, это является ее преимуществом.

Весь процесс пребывания требований в системе разделим на две фазы: фазу ожидания и фазу обслуживания. В фазе ожидания вновь приходящие требования становятся в очередь и ожидают обслуживания. В фазе обслуживания происходит обслуживание заявок из очереди. Время пребывания заявки в системе считается после того, как заявка покинула эту систему обслуженной.

Пусть заявки во входных потоках и поступают в систему с интенсивностями и соответственно. Как отмечалось в главе 1, в хорошую погоду заявки поступают по закону Пуассона. Компьютерное моделирование потоков Пуассона описано в книге [6]. При плохих погодных условиях на дорогах образуются транспортные пачки, математической моделью которых является поток Бартлетта. При моделировании потоков Бартлетта используется следующее: сначала моделируются «медленные» заявки, а затем, согласно распределению (2), за каждой «медленной» заявкой ставится некоторое количество «быстрых» заявок.

Известно, что «медленные» заявки поступают в систему по закону Пуассона с интенсивностью



, (15)

где - это, согласно (3), средняя длина пачки по потоку

Пусть - случайная величина, которая характеризует время обслуживания произвольной заявки, поступающей в систему по закону Пуассона. Эта случайная величина распределена по показательному закону с параметром [1]. Среднее время обслуживания произвольного требования равно:

(16)

Исходя из этих соображений, в изучаемой модели за время обслуживания принимаем некоторое фиксированное значение

(17)

где это интенсивность обслуживания заявок го потока.

Моменты поступления заявок в систему, распределенных по закону Пуассона, случайны и имеют равномерное распределение [7].

Как отмечалось выше, путем имитационного моделирования удается получить оценку среднего времени пребывания произвольной заявки в системе. Для этого вычисляется оценка среднего времени пребывания произвольной заявки в системе по каждому из потоков по формуле (18):

, (18)



где это время пребывания ой заявки в системе по му потоку. Затем вычисляется средневзвешенное время пребывания произвольной заявки в системе по формуле (19):

(19)

Процесс имитационного моделирования изучаемой системы описывается с помощью блок-схем.

Процесс моделирования m числа заявок, распределенных по закону Пуассона, представлен на рисунке 6.

Рисунок 6. Число заявок по закону Пуассона



Процесс моделирования k числа «быстрых» заявок в пачке представлен на рисунке 7.

Рисунок 7. Число «быстрых» заявок в пачке

Моделирование моментов поступления заявок по закону Пуассона представлено на рисунке 8.

Рисунок 8. Моменты поступления заявок по закону Пуассона

Моделирование моментов поступления заявок в потоке Бартлетта рисунке 9.

Рисунок 9. Моменты поступления заявок в потоке Бартлетта



Блок-схемы процессов моделирования фазы ожидания и фазы обслуживания приведены в Приложении A.

С целью построения имитационной модели изучаемой системы и ее оптимизации была разработана программа. Программа реализована в среде разработки Microsoft Visual Studio 2008 на языке программирования C++ с использованием принципов ООП [8]. Перейдем к описанию программы.

2.3 Описание программы. Руководство пользователя

Разработанная программа носит модульный характер и состоит из следующих файлов: Stream.cpp, StreamPuasson.cpp, StreamBartlett.cpp, MerchantDevice.cpp, main.cpp.

Класс Stream - это абстрактный класс входного потока. Файл Stream.cpp, помимо стандартных функций, включает в себя следующие функции:

int getm (double lambdacur) - возвращает число заявок, поступивших в систему на интервале моделирования [0, t].

Класс StreamPuasson - наследник класса Stream, класс входного потока Пуассона. Файл StreamPuasson.cpp, помимо стандартных функций, включает в себя следующие функции:

double *mompostup() - возвращает массив моментов поступления заявок потока Пуассона.

Класс StreamBartlett - наследник класса Stream, класс входного потока Бартлетта. Файл StreamBartlett.cpp, помимо стандартных функций, включает в себя следующие функции:

int getk() - возвращает число «быстрых» машин в пачке;

double *mompostup() - возвращает массив моментов поступления заявок потока Бартлетта.

Класс MerchantDevice - это класс обслуживающего устройства. Файл MerchantDevice.cpp, помимо стандартных функций, включает в себя следующие функции:

void Ozhidaniye (double tOzh, double lambda, double r, double g, int &kappa, double *&T) - функция, в которой моделируется процесс ожидания заявок в очереди;

double Obsluzhivaniye (double tObsl, double lambda, double myu, double r, double g, double Gamma, int &NObsl, int &kappa, double *&T, double &dis) - функция, в которой моделируется процесс обслуживания заявок.

В файле main.cpp моделируется 2 конфликтных входных потока, ОУ и процесс смены режимов ОУ.

Разработанная программа позволяет найти квазиоптимальное (минимальное) средневзвешенное время пребывания произвольной заявки в системе, а также квазиоптимальные параметры управления, соответствующие этому значению. Оптимизация проводится по параметрам t1, t3 (время работы светофора в режимах основного зеленого света в направлении потоков и соответственно) в области изменения параметров от 4 секунд до 120 секунд. Пользователь может изменять указанные границы и шаг перехода к следующему значению параметра. Первым шагом в поиске квазиоптимальных параметров управления является проверка существования стационарного режима в системе при заданной паре (t1, t3) и остальных исходных данных. Полагаем, что стационарного режима заведомо не существует, если очередь хотя бы по одному из потоков превышает 1000 автомобилей. В том случае, если очереди по обоим потокам меньше 1000 автомобилей, то следующим шагом в определении существования стационарного режима при заданных исходных данных является оценка стандартных отклонений и времени пребывания произвольной заявки в системе по 1 и 2 потокам соответственно. Условия для параметров и , при которых полагаем, что стационарный режим существует:

, (20)

где число обслуженных автомобилей го потока, по которым строится статистика, а находится из таблицы значений функции Лапласа при заданной точности. В нашем случае точность полагается равной 0.95, следовательно . Условия (20) получены из интервальной оценки математического ожидания в предположении, что оценка среднего времени пребывания произвольной заявки в системе отклоняется от математического ожидания не более чем на 1 секунду.

Код программы приведен в Приложении B.

Для удобства работы с программой средствами Windows Forms был разработан пользовательский интерфейс. Чтобы начать работу с программой, необходимо запустить файл Diploma.exe. Окно программы представлено на рисунке 10.

Пользователю необходимо ввести исходные данные: выбрать вероятностную структуру входных потоков, задать параметры двух входных конфликтных потоков, выбрать управляющий алгоритм ОУ и ввести оставшиеся параметры ОУ. Описание всех параметров, представленных в окне программы, приведено в «Справке».



Рисунок 10. Окно программы

Чтобы найти квазиоптимальный режим, пользователю необходимо нажать на кнопку «Начать поиск». В результате работы программы пользователю выдаются следующие результаты:

- средневзвешенное квазиоптимальное время пребывания произвольной заявки в системе;

- квазиоптимальное среднее время пребывания произвольной заявки в системе по каждому из потоков;

- квазиоптимальные параметры управления.

Кроме этого, в результате работы программы во вкладке Stationar выводится область существования стационарного режима в системе при заданных исходных данных. Для наглядности этого результата строится матрица специального вида, элементами первой строки которой являются значения t1, а первого столбца - значения t3. Остальные элементы матрицы обозначаются как , где . Элементы закрашивается голубым цветом, если при данных значениях t1, t3 в системе существует стационарный режим. Элемент закрашивается серым цветом, если t1, t3 являются квазиоптимальными. Во вкладках ?1,?2 также выводятся матрицы специального вида. Вид этих матриц описан выше. Однако элементами этих матриц являются значения случайных величин ?1,?2, где средневзвешенное время пребывания произвольной заявки в системе, вычисленное по формуле (19); - оценка среднего времени пребывания произвольной заявки в системе по первому и второму потокам, вычисленная по формуле (18); - оценка среднего числа переключений в режим дополнительного зеленого света за один цикл работы светофора по первому и второму потокам соответственно; ?1,?2 - очередь по первому и второму потокам соответственно к моменту окончания моделирования.

Разработанная программа была апробирована на ряде тестовых примеров. Перейдем к основным результатам.

2.4 Основные результаты

Основные результаты работы программы приведены в таблице 1.

Таблица 1. Основные результаты работы программы

№/ №	1	2	3	4	5	6	7	8	9
1	Погодные условия	Ясно	Ясно	Туман	Ясно	Ясно	Пасмурно	Дождь	Дождь
2	Время суток	00:00-03:00	03:00-06:00	06:00-08:00	08:00-10:00	10:00-12:00	12:00-17:00	17:00-20:00	20:00-00:00
3		0,05	0,01	0,2	0,4	0,3	0,2	0,4	0,2
4		0,05	0,01	0,2	0,4	0,3	0,2	0,4	0,2
5		П	П	4,5	П	П	П	19	19
Циклический алгоритм:
6		4	4	20	25	13	7	81	47
7		4	4	20	25	13	7	79	51
8		5,8	5,7	16,4	21,9	11,5	7,9	121,7	43,3
Алгоритм с дообслуживанием:
9		4	4	4	7 (4)	4	4	13 (4)	11 (4)
10		4	4	4	7 (4)	4	4	10 (4)	8 (4)
11		5,8	5,7	11,0	15,2 (16,0)	9,2	7,0	55,3 (67)	26,3 (28,1)
12		0	0	0,6	2,9 (4,0)	0,9	0,3	4,5 (3,7)	0,9 (0,8)
13		0	0	0,6	2,9 (4,1)	0,9	0,3	4,8 (3,7)	1,1 (0,8)

В таблице 1 это интенсивность поступления заявок в систему в м входном потоке, это математическое ожидание числа заявок в транспортной пачке, буква П означает, что входной поток - поток Пуассона, это квазиоптимальные параметры управления, обозначающие время работы светофора в режиме основного зеленого света в направлении первого и второго потоков соответственно, это минимальное средневзвешенное время пребывания произвольной заявки в системе, это квазиоптимальные параметры управления, обозначающие оценку среднего числа переключений в режим дополнительного зеленого света за один цикл переключений в направлении первого и второго потоков соответственно. В рассматриваемых примерах предполагается следующее: , где это интенсивность обслуживания го входного потока, время работы светофора в режимах желтого света , время работы светофора в режимах дополнительного зеленого света .

Перейдем к анализу полученных результатов. В таблице 1 рассмотрены входные потоки разной интенсивности и разной вероятностной структуры. Во втором и третьем столбцах были выбраны потоки очень малой интенсивности, чтобы показать, что в этом случае алгоритм с дообслуживанием работает как циклический, так как режимы дополнительного зеленого света никогда не наступают ().

Замечено, что чем больше интенсивность входных потоков и чем больше число автомобилей в транспортной пачке, тем эффективнее работает алгоритм с дообслуживанием по сравнению с циклическим алгоритмом. Это отражается в следующем. Во-первых, более чем в 2 раза уменьшается минимальная оценка среднего времени пребывания произвольного автомобиля в системе. Во-вторых, уменьшается минимальный период управления. Это делает алгоритм чувствительным к изменению интенсивности входных потоков. Эти результаты достигаются за счет адаптивности алгоритма с дообслуживанием к изменению интенсивности входных потоков. Об адаптивных свойствах говорят параметры

Также замечено, что если для алгоритма с дообслуживанием в столбцах под номерами 5, 8, 9 выбрать параметры управления , то, несмотря на то, что эти параметры не являются квазиоптимальными, в этих случаях алгоритм с дообслуживанием все равно работает намного эффективнее циклического алгоритма. Таким образом, если в светофоре изначально выставить такие параметры, то не придется следить за изменением интенсивностей и структуры входных потоков. В этом случае светофор сам, за счет адаптивных свойств алгоритма с дообслуживанием, подстроится к управлению входными потоками и будет работать намного эффективнее, чем при использовании циклического алгоритма. Остальные результаты приведены в Приложении C.



Заключение

В работе изучена система управления конфликтными потоками Бартлетта в классе алгоритмов с дообслуживанием.

Данная система представлена как система массового обслуживания с переменной структурой. Процесс управления задан с помощью случайной последовательности, первый элемент которой описывает динамику ОУ, а два других - флуктуации длин очередей по каждому из конфликтных потоков. Изучены вероятностные свойства процесса управления, доказано, что этот процесс является однородной марковской цепью. Получены рекуррентные соотношения для процесса управления, для одномерных распределений. Описано пространство состояний и изучены некоторые свойства этого пространства.

С целью оптимизации работы изучаемой системы была разработана программа, которая позволяет вычислить минимальное средневзвешенное время пребывания произвольной заявки в системе и определить соответствующие этому значению квазиоптимальные параметры управления. Проведено сравнение алгоритма с дообслуживанием с циклическим алгоритмом. Показано, что применение алгоритма с дообслуживанием намного эффективнее в неблагоприятной дорожной обстановке (часы пик, туман, дождь и пр.), а в остальных случаях алгоритм с дообслуживанием работает не хуже циклического алгоритма. Программа носит модульный характер и имеет удобный пользовательский интерфейс.



Список литературы

1. Гнеденко, Б.В. Введение в теорию массового обслуживания / Б.В. Генденко, И.Н. Коваленко. - М.: Издательство ЛКИ, 2013. - 400 с.

2. Кувыкина, Е.В. Общая постановка задачи об алгоритмическом управлении конфликтными потоками заявок при их нелокальном описании / Е.В. Кувыкина // Сборник научных трудов нижегородского филиала института машиноведения РАН. - 2007.

3. Народицкая, Е.В. Выбор последовательности моментов наблюдения при нелокальном описании потоков Бартлетта / Е.В. Народицкая // Труды III конференции молодых ученых НИИ ПМК и факультета ВМК. - 1982.

4. Федоткин, М.А. Оптимальное управление конфликтными потоками и маркированные точечные процессы с выделенной дискретной компонентой / М.А. Федоткин // Лит. матем. сб. - 1988. - т. 28, №4.

5. Чжун, К. Однородные цепи Маркова / К. Чжун. - М.: Мир, 1964. - 428 с.

6. Кофман, А. Массовое обслуживание. Теория и приложения / А. Кофман, Р. Крюон. - М.: Мир, 1965. - 302 с.

7. Феллер, В. Введение в теорию вероятностей и ее приложения, т. 2 / В. Феллер. - М.: Мир, 1984. - 765 с.

8. Шилдт, Г. Искусство программирования на С++ / Г. Шилдт. - СПб.: БХВ-Петербург, 2005. - 496 с.: ил.



Приложения

Приложение А

Блок-схемы





Фаза обслуживания



Фаза ожидания



Приложение Б

Код программы

class Stream

{

protected:

double t; // длительность интервала моделирования

double lambda; // интенсивность поступления заявок в систему

int number; // общее число заявок, поступивших за интервал моделирования

double tOzh; // время на фазу ожидания

double tObsl; // время на фазу обслуживания

double *T; // время пребывания заявок в очереди

int kappa; // число заявок в очереди

int NObsl; // число обслуженных заявок

double myu; // интенсивность обслуживания по потоку

public:

Stream (double t, double lambda);

int getm (double lambdacur); // вычисляет число заявок, поступивших за интервал моделирования

virtual double* mompostup() = 0; // возвращает массив с моментами поступления в систему каждой из заявок

int getnumber(); // возвращает общее число заявок, поступивших за интервал моделирования

~Stream();

};

Stream: Stream (double t, double lambda)

{

this->t = t;

this->lambda = lambda;

this->number = 0;

}

int Stream:getm (double lambdacur)

{

int m = 0;

double eps = 0.01;

double u = ((double) rand()) / RAND_MAX;

double p0 = exp (-lambdacur * t);

double p = p0;

while (u >= (1 - eps))

{

u = ((double) rand()) / RAND_MAX;

}

while (u > p)

{

m = m + 1;

p0 = p0 * lambdacur * t / m;

p = p + p0;

}

return m;

}

int Stream:getnumber()

{

return this->number;

}

Stream:~Stream()

{

}

class StreamPuasson: public Stream

{

public:

StreamPuasson (double t, double lambda):Stream (t, lambda){};

double *mompostup();

~StreamPuasson();

};

double* StreamPuasson:mompostup()

{

double c = 0; // вспомогательная переменная

int m = this->getm (this->lambda);

this->number = m;

double *mompost = new double[m];

for (int i = 0; i < m; i++) // моделирование времени поступления заявок

{

mompost[i] = ((double) rand()) / RAND_MAX * this->t;

}



for (int i = 0; i < m; i++)

{

for (int j = 0; j < m - 1; j++)

{

if (mompost [j + 1] < mompost[j])

{

c = mompost[j];

mompost[j] = mompost [j + 1];

mompost [j + 1] = c;

}

}

}

return mompost;

}

StreamPuasson:~StreamPuasson()

{

}

class StreamBartlett: public Stream

{

protected:

double r; // вероятность поступления более чем одной заявки в пачке

double g; // специальный параметр, связанный со средней длиной пачки

public:

StreamBartlett (double t, double lambda, double r, double g):Stream (t, lambda) {this->r = r; this->g = g;};

int getk(); // число «быстрых» заявок в каждой пачке

double *mompostup(); // моменты поступления всех заявок («быстрых» и «медленных»)

~StreamBartlett();

};

int StreamBartlett:getk()

{

int k = 0;

double eps = 0.01;

double p = 1 - this->r;

double p0 = this->r * (1 - this->g) / this->g;

double u = ((double) rand()) / RAND_MAX;

while (u >= (1 - eps))

{

u = ((double) rand()) / RAND_MAX;

}

while (u > p)

{

k = k + 1;

p0 = p0 * g;

p = p + p0;

}

return k;

}

double* StreamBartlett:mompostup()

{

double ME = (double) (1 + r / (1 - g)); // мат ожидание числа требований в пачке

double lambda_b = lambda / ME; // интенсивность потока медленных заявок

int mmedl = this->getm (lambda_b); // число медленных заявок

double *mompostmedl = new double[mmedl];

if (mmedl == 0)

{

return mompostmedl;

}

for (int i = 0; i < mmedl; i++) // моделирование времени поступления медленных заявок

{

mompostmedl[i] = ((double) rand()) / RAND_MAX * this->t;

}

double c;

for (int i = 0; i < mmedl; i++) // упорядочивание

{

for (int j = 0; j < mmedl - 1; j++)

{

if (mompostmedl [j + 1] < mompostmedl[j])

{

c = mompostmedl[j];

mompostmedl[j] = mompostmedl [j + 1];

mompostmedl [j + 1] = c;

}

}

}

double *minmedl = new double[mmedl];

for (int i = 0; i < mmedl - 1; i++)

{

minmedl[i] = mompostmedl [i + 1] - mompostmedl[i];

}

if (mmedl > 1)

{

minmedl [mmedl - 1] = this->t - mompostmedl [mmedl - 1];

}

double deltamin; // минимальный отрывок времени между поступлением медленных машин

if (mmedl == 1)

{

deltamin = this->t - mompostmedl[0];

}

else

{

deltamin = minmedl[0];

for (int i = 0; i < mmedl; i++)

{

if (deltamin > minmedl[i])

{

deltamin = minmedl[i];

}

}

}

int *etta = new int[mmedl]; // массив для числа быстрых заявок в каждой пачке

int sum = 0;

for (int i = 0; i < mmedl; i++)

{

etta[i] = this->getk();

sum += etta[i];

}

int ettamax = etta[0]; // максимальное число заявок в пачке

for (int i = 0; i < mmedl; i++)

{

if (ettamax < etta[i])

{

ettamax = etta[i];

}

}

ettamax = ettamax + 1; // учет медленной машины

this->number = mmedl + sum;

double *mompost = new double[number];



int temp_etta = 0;

for (int i = 0; i < mmedl; i++)

{

mompost [i + temp_etta] = mompostmedl[i];

for (int p = i + temp_etta + 1; p <= i + temp_etta + etta[i]; p++)

{

mompost[p] = mompost [p - 1] + deltamin / (ettamax + 5);

}

temp_etta += etta[i];

}

delete[] mompostmedl;

delete[] etta;

delete[] minmedl;

mompostmedl = NULL;

etta = NULL;

minmedl = NULL;

return mompost;

}

StreamBartlett:~StreamBartlett()

{

}



class MerchantDevice

{

protected:

double GammaMid; // среднее время пребывания произвольной заявки в ситеме по обоим потокам

int Nmax; // максимальное число заявок, которое необходимо обслужить в направлении каждого из потоков

int potok; // какой тип входного потока выбран (0 - Пуассон, 1 - Бартлетт)

double t1; // длительность режима Г1

double t2;

double t3;

double t4;

double t5;

double t6;

public:

MerchantDevice (int potok, double t1, double t2, double t3, double t4, double t5, double t6);

int GetNmax();

void SetNmax (int m);

void SetGamma1 (double G);

double GetGamma1 ();

void SetGamma2 (double G);

double GetGamma2 ();

void SetGammaMid (double G);

double GetGammaMid ();

void Sett1 (double t);

double Gett1 ();

void Sett2 (double t);

double Gett2 ();

void Sett3 (double t);

double Gett3 ();

void Sett4 (double t);

double Gett4 ();

void Sett5 (double t);

double Gett5 ();

void Sett6 (double t);

double Gett6 ();

void Ozhidaniye (double tOzh, double lambda, double r, double g, int &kappa, double *&T);

double Obsluzhivaniye (double tObsl, double lambda, double myu, double r, double g, double Gamma, int &NObsl, int &kappa, double *&T, double &dis);

~MerchantDevice();

};

MerchantDevice: MerchantDevice (int potok, double t1, double t2, double t3, double t4, double t5, double t6)

{

this->potok = potok;

if (potok == 0)

{

this->Nmax = 10000;

}

else if (potok == 1)

{

this->Nmax = 100000;

}



this->t1 = t1;

this->t2 = t2;

this->t3 = t3;

this->t4 = t4;

this->t5 = t5;

this->t6 = t6;

this->GammaMid = 0;

}

void MerchantDevice: SetNmax (int m)

{

this->Nmax = m;

}

int MerchantDevice: GetNmax()

{

return this->Nmax;

}

void MerchantDevice: SetGammaMid (double G)

{

this->GammaMid = G;

}

double MerchantDevice: GetGammaMid()

{

return this->GammaMid;

}



void MerchantDevice: Sett1 (double t)

{

this->t1 = t;

}

double MerchantDevice: Gett1 ()

{

return this->t1;

}

void MerchantDevice: Sett2 (double t)

{

this->t2 = t;

}

double MerchantDevice: Gett2 ()

{

return this->t2;

}

void MerchantDevice: Sett3 (double t)

{

this->t3 = t;

}

double MerchantDevice: Gett3 ()

{

return this->t3;

}



void MerchantDevice: Sett4 (double t)

{

this->t4 = t;

}

double MerchantDevice: Gett4 ()

{

return this->t4;

}

void MerchantDevice: Sett5 (double t)

{

this->t5 = t;

}

double MerchantDevice: Gett5 ()

{

return this->t5;

}

void MerchantDevice: Sett6 (double t)

{

this->t6 = t;

}

double MerchantDevice: Gett6 ()

{

return this->t6;

}



void MerchantDevice: Ozhidaniye (double tOzh, double lambda, double r, double g, int &kappa, double *&T)

{

int m = 0;

double *mompost;

if (this->potok == 0)

{

StreamPuasson a (tOzh, lambda);

mompost = a.mompostup();

m = a.getnumber();

}

else

{

StreamBartlett b (tOzh, lambda, r, g);

mompost = b.mompostup();

m = b.getnumber();

}

double *T1 = new double [kappa + m];

for (int i = 0; i < kappa; i++)

{

T1 [i] = T[i] + tOzh;

}

for (int i = kappa; i < kappa + m; i++)

{

T1 [i] = tOzh - mompost [i - kappa];

}

if (kappa!= 0)

{

delete[] T;

T = NULL;

}

kappa = kappa + m; // столько заявок стало в очереди

delete[] mompost;

mompost = NULL;

T = T1;

}

double MerchantDevice: Obsluzhivaniye (double tObsl, double lambda, double myu, double r, double g, double Gamma, int &NObsl, int &kappa, double *&T, double &dis)

{

int ksi = (int) (tObsl * myu);

double c = 1.0 / myu; // длительность обслуживания одного требования

double t = tObsl;

int m = 0; // число заявок по потоку Пуассона

double *mompost;

double Tm; // вспомогательная переменная

int s = 0; // сколько заявок на [T - c, T]

int p = 0; // сколько заявок на [mompost, T - c]

double tmp;

double Tcur;

if (this->potok == 0)

{

StreamPuasson a (tObsl, lambda);

mompost = a.mompostup();

m = a.getnumber();

}

else

{

StreamBartlett b (tObsl, lambda, r, g);

mompost = b.mompostup();

m = b.getnumber();

}

double *T1 = new double [kappa + m];

for (int l = 0; l < kappa; l++)

{

T1 [l] = T[l];

}

for (int l = kappa; l < kappa + m; l++)

{

T1 [l] = mompost [l - kappa];

}

if (kappa!= 0)

{

delete[] T;

T = NULL;

}

int i;

if (kappa >= ksi)

{

double *T2 = new double [kappa + m - ksi];

for (int k = 0; k < ksi; k++)

{

tmp = T1 [k]; // вспомогательная операция

T1 [k] = T1 [k] + (k + 1) * c;

tmp = T1 [k]; // вспомогательная операция

dis = (dis * NObsl + T1 [k] * T1 [k])/ (NObsl + 1);

Gamma = (Gamma * NObsl + T1 [k]) / (NObsl + 1);

NObsl = NObsl + 1;

}

for (int k = ksi; k < kappa; k++)

{

tmp = T1 [k]; // вспомогательная операция

T1 [k] = T1 [k] + t; // + tOzh;

tmp = T1 [k]; // вспомогательная операция

T2 [k - ksi] = T1 [k];

}

for (int k = kappa; k < kappa + m; k++)

{

tmp = T1 [k]; // вспомогательная операция

T1 [k] = t - T1 [k]; // + tOzh;

tmp = T1 [k]; // вспомогательная операция

T2 [k - ksi] = T1 [k];

}

kappa = kappa + m - ksi;

delete[] mompost;

delete[] T1;

T = T2;

mompost = NULL;

T1 = NULL;

return Gamma;

}

else if (kappa < ksi && (kappa + m) < ksi)

{

i = 0;

Tm = 0;

while (i < kappa)

{

if (Tm + c <= t - c)

{

tmp = T1 [i]; // вспомогательная операция

T1 [i] = T1 [i] + Tm + c;

tmp = T1 [i]; // вспомогательная операция

dis = (dis * NObsl + T1 [i] * T1 [i])/ (NObsl + 1);

Gamma = (Gamma * NObsl + T1 [i]) / (NObsl + 1);

NObsl = NObsl + 1;

i = i + 1;

Tm = Tm + c;

}

else

{

if ((i + 1) == kappa && m == 0)

{

tmp = T1 [i]; // вспомогательная операция

T1 [i] = T1 [i] + c;

tmp = T1 [i]; // вспомогательная операция

dis = (dis * NObsl + T1 [i] * T1 [i])/ (NObsl + 1);

Gamma = (Gamma * NObsl + T1 [i]) / (NObsl + 1);

kappa = 0;

delete[] mompost;

delete[] T1;

mompost = NULL;

T1 = NULL;

return Gamma;

}

else

{

for (int k = i; k < kappa; k++)

{

tmp = T1 [k]; // вспомогательная операция

T1 [k] = T1 [k] + t;

tmp = T1 [k]; // вспомогательная операция

dis = (dis * NObsl + T1 [k] * T1 [k])/ (NObsl + 1);

Gamma = (Gamma * NObsl + T1 [k]) / (NObsl + 1);

NObsl = NObsl + 1;

}

for (int k = kappa; k < kappa + m; k++) // считаем сколько заявок на [T - c, T]

{

if (T1 [k] > t - c)

{

s++;

}

}

p = m - s;

for (int k = kappa; k < kappa + p; k++)

{

Tcur = t - T1 [k];

dis = (dis * NObsl + Tcur * Tcur)/ (NObsl + 1);

Gamma = (Gamma * NObsl + Tcur) / (NObsl + 1);

NObsl = NObsl + 1;

}

for (int k = kappa + p; k < kappa + m; k++)

{

Tcur = c;

dis = (dis * NObsl + Tcur * Tcur)/ (NObsl + 1);

Gamma = (Gamma * NObsl + Tcur) / (NObsl + 1);

NObsl = NObsl + 1;

}

kappa = 0;

delete[] mompost;



delete[] T1;

mompost = NULL;

T1 = NULL;

return Gamma;

}

}

}

while (Tm + c <= t - c)

{

if (i < kappa + m) // тут были

{

if (T1 [i] <= Tm)

{

Tcur = Tm - T1 [i] + c;