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

На правах рукописи

Букарекко Максим Борисович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ НЕОДНОРОДНЫХ ПРИБОРАХ И РАЗДЕЛЬНЫХ ОЧЕРЕДЯХ НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1' ['0Я /013

Самара - 2013

005538025

Работа выполнена на кафедре «Прикладная математика и информатика» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный технический университет».

Научный руководитель:

Котенко Андрей Петрович,

кандидат физико-математических наук, доцент

Официальные оппоненты:

Ведущая организация:

Тарасов Вениамин Николаевич,

доктор технических наук, профессор, ФГБОУ ВПО «Поволжский государственный университет телекоммуникаций и информатики», кафедра «Программное обеспечение и управление в технических системах», заведующий кафедрой

Коваленко Алексей Гаврилович,

доктор физико-математических наук, профессор ФГБОУ ВПО «Самарский государственный университет», кафедра «Математика и бизнес-информатика», профессор

ФГБОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)»

Защита диссертации состоится «4» декабря 2013 года в 11 часов на заседании диссертационного совета Д 212.217.03 ФГБОУ ВПО «Самарский государственный технический университет» по адресу: 443010, г. Самара, ул. Галактионовская, 141, к. №6, ауд. 33.

С диссертацией можно ознакомиться в библиотеке Самарского государственного технического университета по адресу: 443100, г. Самара, ул. Первомайская, 18, к. №1.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим присылать по адресу: 443100, г. Самара, ул. Молодогвардейская, 244, Главный корпус СамГТУ, ученому секретарю диссертационного совета Д 212.217.03; факс: (846) 278-44-00; E-mail: zoteev-ve@mail.ru

Автореферат разослан «¿j » 2013 г.

Ученый секретарь

диссертационного совета Д 212.217.03, д.т.н.

Зотеев В.Е.

Общая характеристика работы

Актуальность исследования

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

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

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

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

Что касается методов имитационного моделирования, то область применения имеющихся на рынке систем динамического модел1грования (в первую очередь, GPSS World и Matlab Simulink) также ограничена, когда речь идет о СМО рассматриваемого типа, что связано с отсутствием удовлетворительных методов математического описания подобных СМО.

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

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

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

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

В связи с поставленной целью предполагается решить следующие задачи:

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

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

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

4. Реализовать разработанную с использованием конечных автоматов математическую модель массового обслуживания при неоднородных приборах и раздельных очередях в комплексе программ статистического моделирования работы СМО.

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

Методы исследования. Для решения поставленных задач и достижения намеченной цели использованы методы математического моделирования, теории вероятностей, теории автоматов, теории графов.

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

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

2. Предложен метод получения явных уравнений состояния СМО, представленной конечным автоматом, из рекурсивных. Этот подход, в отличие от существующих, позволяет определить состояние системы в произвольный момент времени n+t по последовательности входных сигналов и ее состоянию в произвольный момент времени и, что позволяет снизить затраты машинного времени в ходе статистического моделирования процессов массового обслуживания.

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

4. Создан комплекс программ, позволяющий в отличие от существующих систем динамического моделирования (таких как МаЙаЬ 8шш1шк, ф^) проводить статистическое моделирование процессов массового обслуживания при неоднородных приборах и раздельных очередях, а также реализован алгоритм автоматической визуализации орграфа состояний СМО данного типа.

Положения, выносимые на защиту:

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

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

3. Метод статистического моделирования временных рядов с сохранением структуры стохастической компоненты эмпирического ряда и его применение в рамках статистического моделирования процессов массового обслуживания при неоднородных приборах и раздельных очередях.

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

Теоретическая и практическая значимость исследований.

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

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

3. Реализованная программа автоматического построения орграфа состояний СМО эффективно визуализирует граф в случае трех и более приборов.

4. Разработанные алгоритмы и программы статистического моделирования и автоматического построения графа состояний СМО с неоднородными приборами и раздельными очередями зарегистрированы в фонде программ и алгоритмов Федеральной службы по интеллектуальной собственности (Роспатент).

Достоверность результатов, приведенных в диссертационной работе, обеспечивается: сопоставлением с результатами других исследований; согласованностью с результатами аналитического моделирования в частном случае пуассонов-ских потоков событий; результатами внедрения разработанного комплекса программ отделом коммерческой работы в сфере грузовых перевозок ОАО «РЖД» в рамках проекта по оптимизации работы станций налива нефтепродуктов.

Апробация работы. Результаты научной работы были представлены, обсуждались и докладывались на научных форумах: Российская школа-семинар молодых аспирантов, студентов и молодых ученых «Информатика. Моделирование. Автоматизация проектирования» (Ульяновск, 2010), Вторая Дальневосточная конференция студентов, аспирантов и молодых ученых по теоретической и прикладной математике (Владивосток, 2010), \TI-IX Всероссийская научная конференция с международным участием «Математическое моделирование и краевые задачи» (Самара, 2010, 2011, 2013), 42-я Всероссийская школа-конференция «Со-времешше проблемы математики» (Екатеринбург, 2011), Международная молодежная конференция «Королевские чтения» (СГАУ, Самара, 2011), Международный молодежный научный форум «ЛОМОНОСОВ-2011» (Москва, 2011), Международная молодежная научная конференция по естественнонаучным и техническим дисциплинам «Научному прогрессу - творчество молодых» (Йошкар-Ола, 2012), VIII Всероссийская научно-практическая конференция «Математические модели современных экономических процессов, методы анализа и синтеза экономических механизмов» (Самара, 2013).

Внедрение результатов диссертационного исследования. Разработанные модели, методы и комплекс программ внедрены отделом коммерческой работы в сфере грузовых перевозок Башкирского центра организации работы железнодорожных станций в рамках проекта по созданию автоматической системы управления (АСУ) диспетчеризацией порожних вагонов по станциям налива нефтепродуктов Бензино-Черниковского узла; использованы в учебном процессе кафедры «Прикладная математика и информатика» ФГБОУ ВПО «СамГТУ» и включены в лекционный материал дисциплин «Методы исследования операций», «Дискретная математика», «Теория формальных языков», «Теория вероятностей и математическая статистика».

Публикации. Основные результаты диссертационной работы опубликованы в 20 научных работах, из них 4 статьи в рецензируемых журналах из перечня ВАК и 2 свидетельства Роспатента о государственной регистрации программы для ЭВМ.

Личный вклад автора. Работы [2, 7, 11-19] выполнены самостоятельно, в работах [1, 3-6, 8-10, 20] диссертанту принадлежит совместная постановка задачи, лично соискателем построены решения задач, разработано алгоритмическое и программное обеспечение, выполнены расчеты и анализ результатов.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений, в которых приведены листинг разработашшх программ. Общий объем диссертации составляет 147 страниц, включая 54 рисунка и 14 таблиц. Библиографический список включает 98 наименований.

Содержание работы

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

В первой главе приводится обзор литературы и постановка задач исследования. Проанализировано становление классической теории массового обслуживания и определяется круг задач, которые можно отнести к классическим задачам ТМО; сделаны обзоры работ, посвященных СМО с раздельными очередями и неоднородными приборами.

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

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

При этом СМО с раздельными очередями при неоднородных приборах в условиях недетерминированного входящего потока удалось аналитически смоделировать только в случае упорядоченного входа, когда заявка встает в очередь на

'Артамонов, Г.Т. Ангипггические вероятностные модели функционирования ЭВМ [Текст] / Г.Т. Артамонов, О.М. Брехов. - М: «Энергия», 1978. - 368 с.

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

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

В конце главы на основе проведенного анализа определены задачи диссертационного исследования.

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

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

где щ - пропускная способность, а т, - число мест в очереди /-того канала, / е1,к; к>О, к - количество каналов СМО. Введено понятие диспетчеризации входных заявок. Показано, как изменяется орграф состояний СМО с различимыми каналами при введении диспетчеризации. Предложен следующий протокол диспетчеризации входных заявок: пусть очередная входная заявка обнаруживает систему в состоянии (х1гх2,...,хк; гДе если г-тый канал занят, *,=0, если сво-

боден, у,• соответствует наполненности очереди этого канала, не являющемся состоянием отказа (1,1,...,1;га1,т2,...,»?*). Если существует единственный канал (с номером /), способный принять заявку (0 < у, <|х,»г -II], то заявка направляется к нему. В противном случае оптимальным считаем выбор /-того канала обслуживания, способного обработать заявку с минимальным средним суммарным временем Т обслуживания попавших в него заявок:

тт яГ10'/+1 + */)>

где х> ~ случайная величина, характеризующая незавершённость обработки заявки, находящейся в /-том канале в момент поступления новой заявки, 0<£,<1.

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

Разработана методика математического моделирования СМО с различимыми каналами при указанной детерминированной диспетчеризации, оптимизирующей работу СМО по среднему времени нахождения заявки в системе при минимизации вероятности отказа, и недетерминированной выработкой сигналов на освобождение приборов вероятностным конечным автоматом. Методика описана на примере СМО с двумя неоднородными приборами пропускной способности Ц\>Цг без очереди (сигнатура Т—Т{/.( 1^2,0,ОУ). Ее поведение в дискретном времени п - О, 1, 2, ... представлено недетерминированным конечным автоматом К{8У4) с алфавитом внутренних состояний £={(00),(01),(10),(11)} без выделенных начального и конечного состояний, входным алфавитом А={0,1} и пустым выходным алфавитом. Приведен орграф состояний системы и выведены ее уравнения состояния с нелинейными нестационарными рекурсивными стохастическими булевыми функциями в правой части уравнений состояний НКА

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

.V, (п+1) = а, © ар2 Ф © а^] =а„ФДд(и) ,

э^п +1) = © а^т, ф а252 Ф 52 Ф = уп © ;

яг„ := 6 {ОД}, р„ := ^>2(и)е {0,1};

Уп ■'= Ч(«ЙШ«)е{0,1}, 4, := е {0,1},

где Ф - бинарная операция «исключающее или» алгебры Жегалкина.

Разработан алгоритм получения последовательности состояний СМО по заданной последовательности входных сигналов и начальному состоянию. Явные уравнения состояния конечного автомата позволяют существенно снизить затраты машинного времени на проведение статистического моделирования процессов массового обслуживания. В диссертационной работе показано, как применить данный алгоритм к преобразованию рекурсивных уравнений состояния СМО в различных случаях детерминированной или недетерминированной диспетчеризации при детерминированной или стохастической выработке сигналов на освобождение приборов на примере СМО сигнатуры Т—Т(/л\^12',0,0).

Так, для рассмотренной СМО явные уравнения состояний имеют вид:

2(» + 1) =

ЕГоГш-г (и & и) А (м е 0^1 => ^ = 1)/

л (<5„ = а2 © а^.У] = о)

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

5! (2л+ 2) =

-ат-2 -«=0

(т <п),

= а{2кЦ2к-1) = 1 „

г{2п + 2)=

У к е 1 ,и => = = а(2к)а(2к -1)= 1

л

У к е 1,/я -1 => <?2* =

л

(з1т=о\

где при п > 0 параметры линейной рекурсии заданы последовательностью входных сигналов:

а„+1 :=а(л+1), Д.+, := а{п + 1)а(п), у„+1 := а(и + 1>(?г), <5л+1 := +

Для СМО с недетерминированной диспетчеризацией и стохастической выработкой сигналов на освобождение приборов получены явные уравнения состояния системы:

у,(и + 1) =

.л(Д,=а2Н=0>

= а2(*)=1

л

52(и+ 1) =

Но?-»- ® е =1).

, ч (УкеО,т-\ 8к 1^= йг,(АГ) = 1

л(<5т =оГ("0 = 0),

где

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

у,(и+1) =

,(и +1) =

ЕГо«*-г <-(»«£п)л(у*е0,1я-1=> Д =])л а(/?,„ = 0),

УА"<=0,и=>

где

«,, := Д!(и)а2(и), рп :=а2(я), :=а,(и)я2(и), :=а2(и).

Статистическое моделирование СМО, представлешгой в виде конечного автомата, означает в первую очередь моделирование потоков сигналов 0 гга освобождение заявки прибором и 1 на поступление новой заявки в систему. Под входным сигналом понимается в данном случае эмпирический числовой ряд [Ти 7*2,...Г,-,... Ту, где 7} - интервал времени между г-той и (М)-й по счету буквой 1 или 0. При этом мы сталкиваемся с проблемой, как на основе ограниченных серий наблюдений получить требуемое количество искусственных реализаций. Традиционно при статистическом моделировании учитывается лишь закон распределения интервалов времени между соответствующими сигналами. К такому ряду можно применять методы цифровой обработки сигналов, и получить требуемое количество искусственных реализаций входного сигнала с сохранением структуры эмпирического временного ряда. Предлагаемая методика включает в себя выделение циклов, характерных для входящего потока исследуемой системы, на ос-

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

В третьей главе описан комплекс программ статистического моделирования процессов массового обслуживания при неоднородных приборах и раздельных очередях, а также автоматического построения графа состоят«! данной СМО.

Подробно описан алгоритм разработанного программного комплекса и приведены примеры результатов его работы. Программы зарегистрированы в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности (Роспатент).

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

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

Средняя загруженность /-того прибора рассчитывается как математическое ожидание количества заявок, обслуживаемых у'-тым прибором за данный проме-

і=і,(п+1) / J „

жуток времени к максимально возможному: —1--. Доля отказов

(Л + 1 Xkj+1-kj)

рассчитывается как отношение числа заявок, заставших систему в состоянии St =

к,+1

={mi+l, тг+1, ..., т& 1, ... гп„+1} и пришедішіх за время ~ C0Ilst к

i=k,

суммарному числу заявок, поступивших в систему за указанный интервал времени.

Приведены результаты статистического моделирования при различных законах распределения интервалов времени между поступающими заявками и сигналами на освобождение прибора (усеченном нормальном, экспоненциальном и равномерном). Пример результатов работы программы представлен на рис. 1, 2, где тх - средний интервал времени между поступлениями входящих заявок, Я -интенсивность входящего потока, т- днина такта На оси ординат отложена вероятность отказа /'-того прибора, а на оси абсцисс - модельное время. Каждый столбец гистограммы соответствует равным интервалам времени Г,- длины п г, где г -длина такта, а п - коэффициент, значение которого подбирается для каждой серии реализаций статистической модели исходя из наиболее эффективной визуализации гистограммы.

і

0.8 0.6 0.4 0.2

10 20 30 40 50 Интервал времени Т„ Тщ-7]= 30т

Интервал времени Ті, Ti+J-T,= 300 т

Рисунок 1 - Загруженность 3-го прибора СМО с различимыми каналами сигнатуры Г(0,15;0,05;0,03; 2;4;6) при \1т,. = 0,25 и усеченном нормальном распределении интервалов времени между сигналами

Рисунок 2 - Загруженность 3-го прибора СМО с различимыми каналами сигнатуры Г(0,15;0,05;0,03, 2;4;6) при Л = 0,25 и экспоненциальном распределении интервалов времени между сигналами

В четвертой главе проведена проверка адекватности модели и описано внедрение результатов исследования.

В частном случае пуассоновских потоков событий допустимо проводить аналитическое моделирование работы СМО с различимыми каналами с использованием уравнений Колмогорова. Проведено сравнение результатов аналитического

моделирования процессов массового обслуживания при неоднородных приборах и раздельных очередях с использованием уравнений Колмогорова и статистического моделирования с использованием разработанного комплекса программ. Показано, что результаты статистического моделирования после выхода системы на стационарный режим соответствуют предельным вероятностям состояний, полученных из решения соответствующей системы уравнений Колмогорова. На рис. 3 представлена динамика вероятности отказа трехканальной СМО с различимыми каналами в стационарном режиме. Показано, что разница между средним значением вероятности отказа, вычисленным в ходе статистического моделирования, к предельной вероятностью отказа, полученной из численного решения уравнений Колмогорова, составляет пе более 14%.

Классическую одноканальную СМО с простейшими потоками можно рассматривать как частный случай СМО с неоднородными приборами и раздельными очередями. На рис. 4 приведена динамика вероятности отказа одноканальной СМО без очереди, когда работа СМО вышла на стационарный режим. Отмечено, что разница между средним значением вероятности отказа СМО согласно результатам статистического моделирования и предельной вероятностью отказа, вычисленной с помощью уравнений Колмогорова, составило менее 2%.

Рисунок 3 - Вероятность отказа СМО сигна- рисуНок 4 - Вероятность отказа СМО сигнатуры ДО, 15;0,05;0,03;0,0,0) туры Г(0,15;0)

Адекватность модели также подтверждена результатами внедрения диссертационного исследования в рамках проекта по разработке АСУ диспетчеризации порожних вагонов по станциям налива Бензино-Черниковского узла. Цель, поставленная в ходе внедрения, - спрогнозировать загруженность каждой станции Бензино-Черниковского узла и вероятность отказа на различных временных интервалах. В соответствии с поставленной целью были решены следующие задачи: проведено статистическое моделирование входящего потока, предложен четкий протокол диспетчеризации порожних вагонов, а также проведено тестирование протокола диспетчеризации на стохастических реализациях входящего потока. На основе результатов статистического моделирования работы узла спрогнозирована

динамика нагрузки на каждую станцию, а также динамика вероятности отказа узла в целом. Это позволило подготовить проект изменений в регламент распределения порожних вагонов по станциям налива, которые согласно прогнозу обеспечат снижение среднего времени ожидания вагоном обслуживания на 8%.

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

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

2. Предложен метод получения явных уравнений состояния СМО, представленной конечным автоматом, из рекурсивных, что позволяет определить состояние системы в произвольный момент времени по последовательности входных сигналов и ее состоянию в произвольный момент времени п.

3. Разработан численный метод статистического моделирования потоков СМО, который позволяет на основе имеющейся серии наблюдений получать требуемое количество ее статистических реализаций с сохранением структуры стохастической компоненты.

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

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

6. Реализованные алгоритмы и комплекс программ статистического моделирования внедрены в рамках проекта по созданию АСУ диспетчеризацией порожних вагонов в целях оптимизации работы станций налива.

Список публикаций

В изданиях из перечня ВАК:

1. Букаренко, М.Б. Анализ высоковолатильных рынков с использованием метода Берга и фильтров Чебышева II рода и статистическое моделирование риска убыточности его инструментов [Текст] / М.Б. Букаренко, А.П. Котенко // Вестник Самарского государственного технического университета. Серия: физ.-мат. науки. 2011. №3(24). С. 189-192.

2. Букаренко, М.Б. Система массового обслуживания с различимыми каналами как конечный автомат [Текст] / М.Б. Букаренко, А.П. Котенко // Вестник Са-

марского государственного технического университета. Серия: физ.-мат. науки. 2012. №3(28). С. 114-124.

3. Букаренко, М.Б. Комплекс программ имитационного моделирования работы системы массового обслуживания с неоднородными приборами и раздельными накопителями [Текст] / М.Б. Букаренко, А.П. Котенко // Вестник Самарского государственного технического университета. Серия: физ.-мат. науки. 2013. №2 (31). С. 50-57.

4. Букаренко, М.Б. Явные уравнения состояния системы массового обслуживания, представленной конечным автоматом / М.Б. Букаренко // Вестник Самарского государственного университета. Естественнонаучная серия. 2013. №7(108). С. 10-18.

Патенты и авторские свидетельства:

5. Программа автоматического построения графа состояний системы массового обслуживания с раздельными накопителями и неоднородными приборами [Текст]: Свидетельство о государственной регистрации программы для ЭВМ № 2013616230 Российская Федерация, Федеральная служба по интеллектуальной собственности (РОСПАТЕНТ) / Букаренко М.Б., Котенко А.П.; заявители и правообладатели Букаренко М.Б., Котенко А.П.; заявл. 19.03.2013; per. в реестре программ для ЭВМ 02.07.2013.

6. Программа имитационного моделирования работы системы массового обслуживания с раздельными накопителями и неоднородными приборами [Текст]: Свидетельство о государственной регистрации программы для ЭВМ № 2013616460 Российская Федерация, Федеральная служба по интеллектуальной собственности (РОСПАТЕНТ) / Букаренко М.Б., Котенко А.П.; заявители и правообладатели Букаренко М.Б., Котенко А.П.; заявл. 19.03.2013; per. в реестре программ для ЭВМ 09.07.2013.

В других изданиях:

7. Букаренко, М.Б. Система массового обслуживания с раздельными очередями к каналам / М.Б. Букаренко // Современные проблемы математики: тезисы 42-й Всероссийской школы-конференции (30 января — 6 февраля 2011 г.). - Екатеринбург: Институт математики и механики УрО РАН, 2011. С. 11-13.

8. Букаренко, М.Б. Аналитическое описание систем массового обслуживания с использованием колец вычетов [Текст] / М.Б. Букаренко, А.П. Котенко // Труды VII Всероссийской научной конференции (3-6 июня 2010 г.) «Математическое моделирование и краевые задачи». Часть 2. Моделирование и оптимизация динамических систем и систем с распределенными параметрами. Самара: СамГТУ, 2010. С. 136-140.

9. Букаренко, М.Б. Аналитическое описание систем массового обслуживания с использованием колец вычетов в управлении организационно-экономическими системами [Текст] / М.Б. Букаренко, А.П. Котенко // Сб. ст. «Управление органи-

зационно-экономическими системами: моделирование взаимодействий, принятие решений». Вып. 7. Самара: СГАУ, 2010. С. 31-34.

10. Букаренко, М.Б. Система массового обслуживания с различимыми каналами как конечный автомат [Текст] / М.Б. Букаренко, А.П. Котенко // Труды восьмой Всероссийской научной конференции с международным участием (15-17 сентября 2011 г.) «Математическое моделирование и краевые задачи». Часть 2. Информационные технологии в математическом моделировании. Самара: Сам-ГТУ, 2011. С. 178-181.

11. Букаренко, М.Б. Система массового обслуживания с неоднородными приборами как конечный автомат [Текст] / МБ. Букаренко // Королевские чтения: сб. тр. международной конф. Самара: ООО «БМВ и К», 2011 С. 325-326.

12. Букаренко, М.Б. Совершенствование индикаторов технического анализа на основе спектральных представлений [Текст] / М.Б. Букаренко // Информатика, моделирование, автоматизация проектирования: сб. научн. тр. Ульяновск: УлГТУ, 2010. С. 124-125.

13. Букаренко, М.Б. Получение статистически значимых оценок эффективности механических торговых систем и алгоритмов / М.Б. Букаренко // Вторая Дальневосточная конференция студентов, аспирантов и молодых ученых по теоретической и прикладной математике: материалы конференции. Владивосток: Дальневост. ун-т, 2010. С.35-37.

14. Букаренко, М.Б. Статистическое моделирование входящего потока требований системы массового обслуживания, включающего детерминированную компоненту [Текст] / М.Б. Букаренко // Труды восьмой Всероссийской научной конференции с международным участием (15-17 сентября 2011 г.) «Математическое моделирование и краевые задачи». Часть 2. Моделирование и оптимизация динамических систем и систем с распределенными параметрами. Информационные технологии в математическом моделировании. Самара: СамГТУ, 2011. С. 134— 137.

15. Букаренко, М.Б. Имитационное моделирование входящего потока заявок системы массового обслуживания с детерминироватюй составляющей // Материалы Международного молодежного научного форума «JIOMOHOCOB-2011» / Отв. ред. А.И. Андреев, A.B. Андриянов, Е.А. Антипов, М.В. Чистякова. [Электронный ресурс] — М.: МАКС Пресс, 2011.-1 электрон, опт. диск (DVD-ROM).

16. Букаренко, М.Б. Технический анализ фондового рынка с помощью методов максимальной энтропии и фильтров низких частот [Текст] / М.Б. Букаренко // Математические модели современных экономических процессов, методы анализа и синтеза экономических механизмов. Финансирование и кредитование в экономике России. Методологические и практические аспекты: сб. ст. VIII Всерос. на-учн.-практ. конф. Самара: СГАУ, 2013. Вып. 8. С. 8-14.

17. Букаренко, М.Б. Комплекс программ для автоматического построения графа состояний системы массового обслуживания с раздельными очередями и

неоднородными приборами [Текст] / Международная молодежная научная конференция по естественнонаучным и техническим дисциплинам «Научному прогрессу - творчество молодых» (20-21 апр. 2012 г.): материалы и доклады: в 3 ч. Часть 2. Йошкар-Ола: Поволжский государственный технологический университет, 2012. С. 163-164.

18. Букаренко, М.Б. Алгоритм автоматизированного построения графа состояний системы массового обслуживания с раздельными очередями [Текст] / М.Б. Букаренко // Управление организационно-экономическими системами: моделирование взаимодействий, принятие решений: сборник статей. Самара: СГАУ, 2011.Вып. U.C. 12-15.

19. Букаренко, М.Б. Имитационное моделирование систем массового обслуживания с неоднородными приборами и раздельными очередями с использованием конечных автоматов [Текст] / М.Б. Букаренко // Математические модели современных экономических процессов, методы анализа и синтеза экономических механизмов. Финансирование и кредитование в экономике России. Методологические и практические аспекты: сб. ст. VIII Всерос. научн.-практ. конф. Самара: СГАУ, 2013. Вып. 8. С. 3-8.

20. Букаренко, М.Б. Комплекс программ имитационного моделирования работы системы массового обслуживания с неоднородными приборами и раздельными накопителями [Текст] / М.Б. Букаренко, А.П. Котенко // Труды девятой Всероссийской научной конференции с международным участием (21-23 мая 2013 г.) «Математическое моделирование и краевые задачи». Часть 2. Моделирование и оптимизация динамических систем и систем с распределенными параметрами. Информационные технологии в математическом моделировании. Самара: СамГТУ, 2013. С. 94-97.

Автореферат отпечатан с разрешения диссертационного совета Д 212.217.03 ФГБОУ ВПО «Самарский государственный технический университета (протокол № 16 от «22» октября 2013 г.)

Отпечатано на ризографе. Усл.печ. л. 1,0 Тираж 100 экз. Заказ № 964

ФГБОУ ВПО «СамГТУ» Отдел типографии и оперативной печати 443100, г. Самара, ул. Молодогвардейская, 244

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

На правах рукописи

04201451316

Букаренко Максим Борисович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ НЕОДНОРОДНЫХ ПРИБОРАХ И РАЗДЕЛЬНЫХ ОЧЕРЕДЯХ НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат физико-математически наук, доцент

Котенко Андрей Петрович

Самара - 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..............................................................................................................5

1 ОБЗОР ЛИТЕРАТУРЫ И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ.........10

1.1 Развитие классической теории массового обслуживания..............................10

1.2 Обзор литературы по вопросам аналитического моделирования процессов массового обслуживания при раздельных очередях............................................13

1.3 Обзор литературы по вопросам аналитического моделирования процессов массового обслуживания при неоднородных приборах......................................15

1.4. Обзор литературы по вопросам аналитического моделирования процессов массового обслуживания при неоднородных приборах и раздельных очередях17

1.5 Недостатки классического подхода к моделированию систем массового обслуживания с различимыми каналами..............................................................20

1.6 Актуальность темы и постановка задач исследования..................................23

2 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С РАЗЛИЧИМЫМИ КАНАЛАМИ КОНЕЧНЫМИ АВТОМАТАМИ.....................................................................................................27

2.1 Нотификация систем массового обслуживания.............................................27

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

2.3 СМО с детерминированной диспетчеризацией и недетерминированной выработкой сигналов на освобождение приборов. Моделирование вероятностным КА.................................................................................................36

2.4 СМО с детерминированной диспетчеризацией и недетерминированной выработкой сигналов на освобождение приборов. Избавление от стохастичности и моделирование детерминированным КА................................40

2.5 СМО с детерминированной диспетчеризацией и детерминированной выработкой сигналов на освобождение приборов...............................................50

2.6 СМО с недетерминированной диспетчеризацией и стохастической выработкой сигналов на освобождение приборов...............................................54

2.7 СМО с недетерминированной диспетчеризацией и детерминированной выработкой сигналов на освобождение приборов. Моделирование вероятностным КА.................................................................................................57

2.8 СМО с недетерминированной диспетчеризацией и детерминированной выработкой сигналов на освобождение приборов. Моделирование детерминированным КА........................................................................................60

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

3 КОМПЛЕКС ПРОГРАММ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ И АВТОМАТИЧЕСКОГО ПОСТРОЕНИЯ ГРАФА СОСТОЯНИЙ ПРОЦЕССОВ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ НЕОДНОРОДНЫХ ПРИБОРАХ И РАЗДЕЛЬНЫХ ОЧЕРЕДЯХ..................................................................................68

3.1 Программа автоматического построения графа состояний СМО с неоднородными приборами и раздельными очередями без диспетчеризации... 68

3.2 Программа автоматического построения графа состояний СМО с неоднородными приборами и раздельными очередями с диспетчеризацией .... 78

3.3 Комплекс программ статистического моделирования процессов массового обслуживания при неоднородных приборах и раздельных очередях.................82

4 ПРОВЕРКА АДЕКВАТНОСТИ МОДЕЛИ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЯ...............................................................................................100

4.1 Сравнение результатов статистического и аналитического моделирования процессов массового обслуживания при неоднородными приборах и раздельных очередях............................................................................................100

4.2 Одноканальная СМО как частный случай СМО с различимыми каналами...............................................................................................................105

4.3 Внедрение результатов исследования...........................................................108

ЗАКЛЮЧЕНИЕ....................................................................................................111

ЛИТЕРАТУРА......................................................................................................113

ПРИЛОЖЕНИЕ А. ЛИСТИНГ ПРОГРАММЫ АВТОМАТИЧЕСКОГО ПОСТРОЕНИЯ ГРАФА СОСТОЯНИЙ СМО С НЕОДНОРОДНЫМИ ПРИБОРАМИ И РАЗДЕЛЬНЫМИ ОЧЕРЕДЯМИ С НЕДЕТЕРМИНИРОВАННОЙ ДИСПЕТЧЕРИЗАЦИЕЙ........................... 126

ПРИЛОЖЕНИЕ Б. ЛИСТИНГ ПРОГРАММЫ АВТОМАТИЧЕСКОГО ПОСТРОЕНИЯ ГРАФА СОСТОЯНИЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С НЕОДНОРОДНЫМИ ПРИБОРАМИ И РАЗДЕЛЬНЫМИ ОЧЕРЕДЯМИ С ДЕТЕРМИНИРОВАННОЙ ДИСПЕТЧЕРИЗАЦИЕЙ............132

ПРИЛОЖЕНИЕ В. ЛИСТИНГ М-ФАЙЛОВ МОДЕЛИРОВАНИЯ ПОТОКОВ СОБЫТИЙ ПРОГРАММЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ НЕОДНОРОДНЫХ ПРИБОРАХ И РАЗДЕЛЬНЫХ ОЧЕРЕДЯХ.......................................... 139

ПРИЛОЖЕНИЕ Г. СВИДЕТЕЛЬСТВО О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ №2013616230........................ 142

ПРИЛОЖЕНИЕ Д. СВИДЕТЕЛЬСТВО О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ №2013616460........................ 143

ПРИЛОЖЕНИЕ Е. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ......................................................144

ВВЕДЕНИЕ

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

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

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

На данный момент, все методы исследования СМО можно разделить на аналитические и статистические. Для практически распространенного случая систем массового обслуживания с приборами разной производительности и независимыми индивидуальными накопителями для каждого прибора (встречающихся в области параллельных вычислений, оптимизации архитектуры сложных ЛВС и пр.) аналитические методы применимы только в частных случаях: упорядоченного входного потока, отсутствия адаптивной диспетчеризации и т.д. Особо следует отметить, что подавляющее большинство аналитических методов предполагают, что потоки в системе являются либо простейшими, либо допускают аппроксимацию таковыми.

Что касается методов статистического и имитационного моделирования, то область применения имеющихся на рынке систем динамического моделирования также ограничена, когда речь идет о СМО неклассического типа. Наиболее разработанной в этом плане является GPSS (General Purpose Simulation System) - общецелевая система имитационного моделирования (СИМ), предназначенная для разработки моделей сложных систем с дискретным и непрерывным характером функционирования и проведения экспериментов с целью изучения свойств и закономерностей процессов, протекающих в них, а также выбора наилучшего проектного решения среди нескольких возможных вариантов.

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

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

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

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

Научная новизна диссертационной работы заключается как в предмете, так и в объекте исследования. Автором не было найдено ни одной работы, в которой бы подобные системы массового обслуживания рассматривались для произвольного числа приборов с ограниченными емкостями накопителей при неупорядоченном входе или выбором прибора, отличного от случайного, ни аналитическими методами, ни методами статистического моделирования. Также не было найдено ни одной работы, в которой содержалась бы сколько-нибудь разработанная методика описания систем или сетей массового обслуживания конечными автоматами. Таким образом, научная новизна работы определяется следующим:

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

2. Предложен метод получения явных уравнений состояния СМО, представленной конечным автоматом, из рекурсивных. Этот подход, в отличие от существующих, позволяет определить состояние системы в произвольный момент времени п+1 по последовательности входных сигналов и ее состоянию в произвольный момент времени п, что позволяет снизить затраты машинного

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

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

4. Создан комплекс программ, позволяющий в отличие от существующих систем динамического моделирования (таких как Matlab Simulink, GPSS) проводить статистическое моделирование процессов массового обслуживания при неоднородных приборах и раздельных очередях, а также реализован алгоритм автоматической визуализации орграфа состояний СМО данного типа.

Актуальность темы диссертационного исследования обусловлена следующим:

1) практической распространенностью на практике рассматриваемой модели массового обслуживания;

2) отсутствием удовлетворительных методов аналитического моделирования процессов массового обслуживания рассматриваемого типа в общих случаях;

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

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

Диссертационное исследование разделено на 4 главы. В первой главе обосновывается актуальность темы, ставятся цель и задачи исследования, а также приводится обзор литературных источников. Во второй главе ставится задача получения и исследования уравнений состояния исследуемого типа СМО с точки зрения теории конечных автоматов, вводится понятие диспетчеризации, а также на конкретных примерах разбирается весь ход составления

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

1 ОБЗОР ЛИТЕРАТУРЫ И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

Большинство СМО на практике относятся к системам, которые не могут быть описаны простым графом гибели-размножения [1]. Наглядным примером таких СМО является модель массового обслуживания с частичной взаимопомощью между каналами [2]. Не только решение, но и составление систем дифференциальных уравнений, а также построение графа состояний для подобных СМО большой размерности возможно осуществить только компьютерными методами. Предметом исследования диссертации являются системы массового обслуживания с различимыми приборами, относящиеся именно к таким системам. Под СМО с различимыми приборами мы будем понимать системы с неоднородными приборами, т.е. такие СМО, в которых хотя бы два прибора имеют различную производительность, при раздельных очередях к приборам. Эти типы систем объединяет то, что они не могут быть представлены орграфом процесса гибели-размножения и требуют введения понятия диспетчеризации, т.е. алгоритма распределения входящих заявок по обслуживающим приборам.

1.1 Развитие классической теории массового обслуживания

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

Наиболее важным событием в истории теории вероятностей с момента выхода в свет цикла работ Хинчина [3, 4, 5, 6, 7, 8, 9] явилось осознание того, что теория массового обслуживания логически вытекает из теории марковских процессов, а теоретическим аппаратом для изучения СМО должен являться аппарат марковских цепей. Особую роль в теории массового обслуживания играет эргодическая теория цепей и процессов Маркова. Условия эргодичности цепи Маркова в виде, весьма удобном в приложения к теории массового обслуживания, были выяснены в работе [10]. В работе [И] исследовано распределение

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

Важнейшим результатом применения аппарата марковских цепей явилось упрощение многих моделей СМО с помощью процесса гибели-размножения, т.е. марковского, обычно однородного, процесса со счетным упорядоченным множеством состояний, когда в момент изменения состояния процесса с вероятностью 1 происходит переход в предыдущее или следующее состояние. Ключевой работой в этом смысле явилась работа [13], где были введены необходимые и достаточные условия эргодичности процесса. Используя аппарат процессов гибели-размножения, в [14] впервые были рассмотрены неоднородные процессы в СМО. К этому же этапу относится и применение в теории массового обслу