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

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

ТИТОВ Сергей Викторович

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПРИНЯТИЯ РЕШЕНИЙ В СЕТЕВЫХ СИСТЕМАХ ОБСЛУЖИВАНИЯ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ

МЕТОДОВ

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

методы и комплексы программ

АВТОРЕФЕРАТ

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

Воронеж — 2005

Работа выполнена в Воронежском государственном техническом университете

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

доктор технических наук, профессор Бурковский Виктор Леонидович

Официальные оппоненты: доктор технических наук, профессор

Леденева Татьяна Михайловна;

кандидат технических наук, доцент Жданов Алексей Алексеевич

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

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

Защита состоится «10» ноября 2005 г. в 10 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 Воронежского государственно -го технического университета по адресу: 394026, г. Воронеж, Московский просп., 14.

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

Автореферат разослан «10» октября 2005 г.

Ученый секретарь диссертационного совета

Питолин В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

I РОС. НАЦИОНАЛЬНАЯ

• разработку схемы кодирования хромосом возможных решений, функций перехода из пространства представлений в пространство объектов;

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

• анализ вариантов параметров генетического алгоритма и выбор наилучших;

• разработка графической среды построения моделей, визуализирующей структуру исследуемой системы и взаимодействие входящих в нее подсистем;

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

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

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

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

• комплексная имитационная модель процессов функционирования сетей массового обслуживания, позволяющая осуществлять оперативную адаптацию модулей моделирования к специфическим особенностям конкретной объектной области;

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

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

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

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

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

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

Ожидаемый годовой экономический эффект, полученный при внедрении результатов диссертации в ОАО «Елецкий крупяной завод», составляет 523 тыс. р. в ценах 2005 года. Эффект достигается за счет уменьшения времени простоя производственных линий, уменьшения объема отложенного обслуживания, увеличения объема переработки наиболее приоритетных типов сырья

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

Апробация работы. Основные результаты докладывались и обсуждались на Международной научно-практической конференции «Теория активных систем» (Москва, 2001); VI Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2001); региональной научно-технической конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2002-2003); Международной конференции СССУ/НТСЗ 2003 «Современные сложные системы управления», Всероссийской научно-технической конференции «Информационные технологии» (Воронеж, 2005), а также на научных семинарах кафедры автоматизированных и вычислительных систем.

Публикации. По результатам исследований опубликовано 14 научных работ. В работах, опубликованных в соавторстве, лично соискателем предложены: в работе [3] - формализованное описание процессов взаимодействия неоднородных потоков заявок в сетевых системах массового обслуживания; в

[6,10] - подход к имитационному моделированию сетевых систем со сложным поведением заявок; в [8,9,11,12,13] - эволюционный подход к задаче оптималь- ' ного управления СеМО; в [4,5,7,14] - программное обеспечение моделирования, анализа и оптимального управления сетями массового обслуживания; в [1,2] - практическая применимость комплексной имитационной системы моделирования и анализа.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 127 наименований и трех приложений на 14 страницах. Основная часть работы изложена на 138 страницах, содержит 54 рисунка и 22 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рассматривается задача моделирования СеМО, в которых имеет место индивидуализированное поведение заявок. Примером таких систем могут служить поликлинические отделения, транспортные системы, многофазные производственные системы и др. Особенностью функционирования таких систем является наличие поведения у требований на обслуживание, что позволяет сказать, что мы имеем дело с «интеллектуальными» заявками. Наличие «интеллектуальности» у заявок не позволяет задать маршруты потоков требований в виде матриц вероятностей переходов, т.к. вместо того, чтобы из прибора / перейти к прибору у с вероятностью р5, заявка может «предпочесть» посетить другой' прибор или покинуть систему в зависимости от каких-либо дополнительных условий (например слишком длинной очереди перед прибором у).

При классическом дискретно-событийном моделировании СеМО с несколькими типами заявок на каждом этапе цикла моделирования оперируют многомерным вектором состояния сети, т.е. состояние /-го узла в каждый момент времени определяется вектором где #<,(/) - номер типа требования, стоящего в узле / нау'-м месте. l<,NlJ(t)йQг 1 < / <, Я, 1 ^ у й и,, п, > 1. Однако вследствие наличия индивидуального поведения у заявок информации, хранимой в векторе состояния сети, недостаточно, поэтому использование такого подхода не представляется возможным.

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

Р'=

Ри Ргх ••• РтЛ Кг Рг.2 ••• Рм.1

(1)

^и Л* •• Р-

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

По матрице Р при генерации очередной заявки можно определить вектор посещения приборов обслуживания В = {Ь1гЬ2,..., Ья}, где Ь, принимает значение О, если данная заявка не должна в будущем посещать обслуживающий прибор /, либо 1, если она должна его посетить. После окончания обслуживания заявки в /-м приборе соответствующее значение Ь, должно измениться с 1 на О Условием завершения обслуживания данной заявки является равенство нулю всех элементов вектора В~. После этого она помещается в поток обслуженных заявок.

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

5

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

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

очередь перед прибор обслужи-

прябором ваяия

;

очередь перся прибор обсяужи-

првбороы вания

уровень 0 уровень 1 уровень N

Рис. 1. Древовидная структура модели

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

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

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

ста от выходных связей прибора; обновление состояния каналов на каждом этапе цикла моделирования.

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

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

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

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

Рис 2. Алгоритм маршрутизации заявки из обслуживающего прибора

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

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

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

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

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

где и - количество классов заявок; к, - коэффициент значимости /'-го класса; т, - количество обслуженных заявок /-го класса.

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

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

л

(3)

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

'1 П1 ¡2 ¡2 щ

Рис. 3. Структура хромосомы: з, - номер перенастраиваемого прибора на г-м временном интервале, п, - номер целевого класса заявок Однако при скрещивании и мутации таких индивидов могут получиться некорректные решения, т.е. графики перенастройки, которые невозможно реализовать в физической системе. Поэтому осуществим дальнейшую декомпозицию структуры хромосомы. Будем считать процедуры переключения приборов обслуживания независимыми с точки зрения взаимного влияния друг на друга. Это позволяет разделить совокупное расписание на С отдельных для каждого прибора расписаний. Таким образом, хромосома превращается в матрицу, изображенную на рис. 4. Каждая строка матрицы соответствует определенному прибору обслуживания и представляет собой график переключения этого приборе на всем интервале моделирования. В ячейках расположены номера классов заявок, на которые осуществляется перенастройка.

прибор график переключения

»и Пп ... »1к

п21 П22 ... »2к

...

пС1 "с? ... Пек

Рис 4. Декомпозиция структуры хромосомы: С - количество приборов обслуживания, к - количество отрезков временного интервала, пц- номер целевого класса заявок

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

Рис. 5. Пример оператора мутации

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

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

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

ц раз (то есть интервал разбивается ьа — равных отрезков), а затем применим

Я

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

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

11

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

Программный комплекс состоит из следующих модулей:

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

2) модули редактирования свойств и параметров элементов модели;

3) процедуры записи модели на диск в виде файла и чтения модели с диска;

4) подсистема имитационного моделирования;

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

6) подсистема сбора статистической информации;

7) подсистема отображения результатов моделирования и собранной статистики в виде наглядных графиков и диаграмм;

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

Разработанное программное обеспечение зарегистрировано в Государственном фонде алгоритмов и программ (per. № 50200100217).

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

Модель медсанчасти ОАО «СГОК» представляет собой стохастическую сеть, структура которой представлена на рис. 6. Обслуживающие каналы модели будут представлять врачей-специалистов поликлиники. Целесообразно объединять нескольких врачей одной специальности в многоканальный обслуживающих прибор (чтобы можно было оценить количество врачей определенной специальности, достаточных для обслуживания моделируемого потока заявок)

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

По результатам моделирования можно сделать вывод, что в целом работа поликлиники проходит сбалансировано: все поступившие на обслуживание заявки были обработаны, не наблюдается длинных очередей, сильно перегруженных врачей. Загруженность врачей составляет 60-70 %. Максимальные длины очередей в несколько раз меньше аналогичных показателей в государственной системе здравоохранения. Таким образом, имеется резерв по нагрузке врачей на приеме в поликлинике. Следует обратить внимание на узкое место: загрузка врачей-отоларингологов составляет 90 %, средняя длина очереди к отоларингологам самая большая в системе, а максимальная длина равна количеству мест для ожидания. Для повышения эффективноста функционирования поликлинического отделения медсанчасти необходимо устранить это узкое место системы.

Рис. 6. Модель поликлиники медсанчасти ОАО «СТОК»

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

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

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

•* ИСУ - KCifiOhH.jt.mill ш ГХ|

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

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

На рис. 8 изображен эволюционный процесс в виде графиков роста приспособленности среднего, худшего и лучшего индивида на протяжении 1783 поколений Лучший найденный график перенастройки производственных линий повышает эффективность работы производственной системы почти в два раза. Ожидаемый годовой экономический эффект составляет 523 тыс. р. в ценах 2005 года.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6 На основе созданных моделей и алгоритмов разработано программное обеспечение моделирования, анализа "и оптимального управления сетями массового обслуживания.

Основные теоретические и практические результаты работы прошли успешную проверку при моделировании и оптимизации ОАО «Елецкий крупяной завод». Экономический эффект достигается за счет уменьшения времени простоя производственных линий, уменьшения объема отложенного обслуживания, увеличения объема переработки наиболее приоритетных типов сырья.

Основные результаты диссертации опубликованы в следующих работах:

1. Абсатаров P.A., Бурковский A.B., Титов C.B. Структура информационной системы управления многопрофильным медицинским учреждением // Новые технологии в научных исследованиях, проектировании, управлении, производстве: Тр. регион, науч.^ехн. конф. - Воронеж, 2002. С. 60-61.

2. Абсатаров P.A., Титов C.B., Высочкин Д.Н. Результаты практической апробации системы моделирования и анализа потоков заявок // Системы управления и информационные технологии: Междунар. сб. тр. - Воронеж: «Научная книга», 2003. Вып. 10. С. 43-48.

3. Абсатаров P.A., Титов C.B., Высочкин Д.Н. Формализованное описание основных элементов системы моделирования и анализа функциональной структуры многопрофильного лечебного комплекса // Системы управления и информационные технологии: Междунар. сб. тр. - Воронеж: «Научная книга», 2003. Вып. 11. С. 96-100.

4. Бурковский B.JL, Елецких C.B., Титов C.B. Инструментальная система имитационного моделирования и анализа технологических структур производства сыпучих продуктов. Регистрационный номер 50200100217 от 05.06.2001. Государственный фонд алгоритмов и программ. М., 2001.

5. Бурковский В.Л., Елецких C.B., Титов C.B. Программный комплекс моделирования и оптимизации технологических структур производства сыпучих пищевых продуктов // Теория активных систем: Тр. Междунар. науч.-пракг. конф. - Москва: Институт проблем управления РАН, 2001. Т. 2. С. 54.

6. Бурковский В.Л., Титов C.B. Имитационное моделирование многопрофильного лечебного учреждения на основе разомкнутых стохастических сетей // Вестник Воронеж, гос. техн. ун-та. Сер. Вычислительные и информационно-телекоммуникационные системы. - 2002. Вып. 8.2. С. 86-88

7. Бурковский B.JL, Титов C.B. Информационная система управления многопрофильным лечебным комплексом. Регистрационный номер 50200200236 от 13.05.2002. Государхгтвенный фонд алгоритмов и программ. М., 2002.

8. Бурковский B.JI. Титов C.B. Алгоритм вычисления вектора долей семейства конкурирующих шаблонов, инвариантный длине бинарной строка, на основе уточненной теоремы о шаблонах II Системы управления и информационные технологии: Науч.-техн журнал. - Воронеж: Научная книга, 2003. № 1-2 (12). С. 15-19.

9. Бурковский B.JI. Титов C.B. Анализ применения генетических алгоритмов для решения задач планирования расписаний в СеМО // Системы управления и информационные технологии: Науч.-техн. журнал. - Воронеж-Научная книга, 2005. № 3 (20).С. 33-36.

10. Бурковский В.Л., Титов C.B., Имитационное моделирование технологических процессов переработки сыпучих материалопотоков // Новые технологии в научных исследованиях, проектировании, управлении, производстве: Тр. регион науч.-техн. конф. - Воронеж, 2003. С. 48.

И. Бурковский B.JI., Титов C.B., Использование эволюционных методов оптимизации при принятии решений в системах управления переработкой сыпучих пищевых продуктов // Междунар. конф. СССУ/HTCS 2003 Современные сложные системы управления: Сб. науч. тр. Т. 2. С. 273.

12 Бурковский B.JI., Титов С.В Оптимизация стохастических сетей эволюционными методами поиска // Электротехнические комплексы и системы управления- Межвуз. сб. науч. тр. - Воронеж: ВГТУ, 2003. С. 77-81.

13 Бурковский B.JI. Титов C.B. Эволюционный подход к планированию расписаний в сетях массового обслуживания И Информационные технологии 2005: Материалы Всерос. науч.-техн. конф. - Воронеж: Научная книга, 2005. -С. 183-186.

14. Титов C.B., Елецких C.B. Программное обеспечение машинного моделирования и анализа технологических структур производства сыпучих пищевых продуктов И Современные проблемы информатизации в технике и технологиях: Тр. VI Междунар. открытой науч. конф. - Воронеж, 2001. С. 27-28.

Подписано в печать 7 октября 2005. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ № ч&А

Воронежский государственный технический университет . 394026, г. Воронеж, Московский просп., 14

I

ь

L

N21 8 6 5 1

PI 1Б Русс.:;!,";

2006-4 16878

ПЕРЕЧЕНЬ УСЛОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. СЕТИ МАССОВОГО ОБСЛУЖИВАНИЯ И ЭВОЛЮЦИОННЫЕ МЕТОДЫ ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ.

1.1. Состояние и тенденции развития теории массового обслуживания.

1.2. Анализ эволюционных методов поиска оптимальных решений.

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

Цель работы и задачи исследования.

Выводы.

ГЛАВА 2. АГЕНТНОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

2.1. Технология агентного имитационного моделирования.

2.2. Алгоритмы имитационного моделирования.

2.3. Статистическая обработка результатов моделирования.

Выводы.

ГЛАВА 3. ОПТИМИЗАЦИЯ СеМО НА ОСНОВЕ ЭВОЛЮЦИОННЫХ МЕТОДОВ.

3.1. Выбор критерия оптимальности.

3.2. Разработка способа кодирования хромосомы.

3.3. Вычисление минимального размера популяции.

3.4. Разработка генетических операторов.

3.5. Поколенческий генетический алгоритм.

3.6. Подбор параметров генетического алгоритма.

Выводы.

ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

4.1. Структура программного комплекса моделирования и оптимизации.

4.2. Объектно-ориентированное представление модели.

4.3. Модуль графического редактирования модели.

4.4. Графический интерфейс пользователя.

4.5. Анализ результатов моделирования.

Выводы.

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

5.1. Имитационное моделирование СеМО на примере медико-санитарной части ОАО «СГОК».

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

АКТУАЛЬНОСТЬ ТЕМЫ

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

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

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

ЦЕЛЬ РАБОТЫ

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

Исходя из данной цели, в работе определены следующие задачи исследования:

• разработка формализованного описания процессов взаимодействия неоднородных потоков заявок в сетях массового обслуживания;

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

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

• разработку схемы кодирования хромосом возможных решений, функций перехода из пространства представлений в пространство объектов;

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

• анализ вариантов параметров генетического алгоритма и выбор наилучших;

• разработка графической среды построения моделей, визуализирующей структуру исследуемой системы и взаимодействие входящих в нее подсистем;

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

МЕТОДЫ ИССЛЕДОВАНИЯ Методы исследования основаны на использовании теории массового обслуживания, эволюционных методов, теории вероятностей, дискретной математики, теории графов, вычислительной математики, объектно-ориентированного программирования, компьютерных технологий.

НАУЧНАЯ НОВИЗНА

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

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

• комплексная имитационная модель процессов функционирования сетей массового обслуживания, позволяющая осуществлять оперативную адаптацию модулей моделирования к специфическим особенностям конкретной объектной области;

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ

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

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

РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

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

Ожидаемый годовой экономический эффект, полученный при внедрении результатов диссертации в ОАО «Елецкий крупяной завод», составляет 523 тыс. руб. в ценах 2005 года. Эффект достигается за счет уменьшения времени простоя производственных линий, уменьшения объема отложенного обслуживания, увеличения объема переработки наиболее приоритетных типов сырья.

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

АПРОБАЦИЯ РАБОТЫ

Основные результаты докладывались и обсуждались на международной научно-практической конференции «Теория активных систем» (Москва, 2001);

VI Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2001); региональной научно-технической конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 20022003); международной конференции CCCY/HTCS 2003 «Современные сложные системы управления», всероссийской научно-технической конференции «Информационные технологии» (Воронеж, 2005), а также на научных семинарах кафедры автоматизированных и вычислительных систем.

ПУБЛИКАЦИИ

По результатам исследований опубликовано 14 научных работ. В работах, опубликованных в соавторстве и приведенных в конце диссертации, лично соискателем предложены: в работе [4] - формализованное описание процессов взаимодействия неоднородных потоков заявок в сетевых системах массового обслуживания; в [17,21] - подход к имитационному моделированию сетевых систем со сложным поведением заявок; в [19,20,22,23,24] - эволюционный подход к задаче оптимального управления СеМО; в [15,16,18,61] -программное обеспечение моделирования, анализа и оптимального управления сетями массового обслуживания; в [2,3] - практическая применимость комплексной имитационной системы моделирования и анализа.

СТРУКТУРА И ОБЪЕМ РАБОТЫ Диссертация состоит из введения, пяти глав, заключения, списка литературы из 127 наименований и трех приложений на 14 страницах. Основная часть работы изложена на 138 страницах, содержит 54 рисунка и 22 таблицы.

Выводы

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

2. Разработанные структуры данных для эффективного хранения компонентов имитационной модели и манипулирования списками элементов и параметрами модели в оперативной памяти ЭВМ предоставляют возможность эффективной организации процедур прямого и обратного преобразования представления модели между соответствующими полями информационного пространства;

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

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

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

5.1. Имитационное моделирование СеМО на примере медико-санитарной части ОАО «СГОК»

Медико-санитарная часть открытого акционерного общества «Стойленский горно-обогатительный комбинат» (ОАО «СГОК») предназначена для оказания амбулаторно-поликлинической, лечебно-диагностической, стационарной и скорой помощи не только работающим на данном производстве, но и жителям г. Старый Оскол. Медико-санитарная часть состоит из поликлиники, мощностью 250 посещений в смену, стационара на 120 коек, мощного лечебно-диагностического отделения. Кроме того, при медсанчасти имеется дневной стационар на 40 коек, реанимационное отделение платных услуг и служба скорой помощи. На рис. 5.1 представлена упрощенная структурная схема учреждения.

Рис. 5.1. Упрощенная структура медсанчасти Стойленского ГОКа

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

Основные теоретические и практические результаты работы прошли успешную проверку при моделировании и оптимизации ОАО «Елецкий крупяной завод». Ожидаемый годовой экономический эффект составляет 523 тыс. руб. в ценах 2005 года; он достигается за счет уменьшения времени простоя производственных линий, уменьшения объема отложенного обслуживания, увеличения объема переработки наиболее приоритетных типов сырья.

1. Абсатаров Р.А. Медсанчасть как системный объект управления. -типография ОАО «Стойленский ГОК», 2001. - 163 с.

2. Абсатаров Р.А., Титов С.В., Высочкин Д.Н. Результаты практической апробации системы моделирования и анализа потоков заявок. Международный сборник трудов «Системы управления и информационные технологии». Выпуск 10. Воронеж: «Научная книга», 2003.

3. Александров Е.Е. Оптимизация многоканальных систем управления. -Харьков: Основа, 1996. 288 с.

4. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Воронеж: ВГТУ, 1995. - 69 с.

5. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов / Межвуз. сб. "Высокие технологии в технике, медицине и образовании" Часть 3. Воронеж: ВГТУ, 1997.

6. Батищев Д.И., Исаев С.А., Ремер Е.К. Решение задач нелинейного программирования с помощью генетических алгоритмов. / Тез.докл. на Всеросс. совещании-семинаре "Высокие информационные технологии в региональной информатике" Часть 1. Воронеж: ВГТУ, 1998.

7. Батищев Д.И., Исаев С.А., Ремер Е.К. Эволюционно-генетический подход к решению задач невыпуклой оптимизации. / Тез. докл. на Всеросс. совещании-семинаре "Высокие информационные технологии в региональной информатике" Часть 1. Воронеж: ВГТУ, 1998.

8. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно генетических алгоритмов / Мужвуз. сборник. - Воронеж: ВГТУ, 1994.

9. Башарин Г.П. Массовое обслуживание в телефонии / Г.П. Башарин, А.Д. Харкевич, М.А. Шнепс . М.: Наука, 1968. - 464 с.

10. Беляева С.И. Имитационное моделирование систем массового обслуживания. Горький: ГПИ, 1988. - 52 с.

11. Боровиков А.А Вероятностные процессы в теории массового обслуживания. М.: Наука, 1972. -288 с.

12. Бронштейн О.И., Веклеров Е.Б. Об одной управляемой системе обслуживания // Изв. АН СССР. Техн. кибернетика. 1967. - № 5. - с. 101-105

13. Бурковский В.Л., Елецких С.В., Титов С.В. Инструментальная система имитационного моделирования и анализа технологических структур производства сыпучих продуктов. М.: ФАП ВНТИЦ, 2001. № госрегистрации 50200100217 от 05.06.2001.

14. Бурковский В.Д., Титов С.В. Имитационное моделирование многопрофильного лечебного учреждения на основе разомкнутых стохастических сетей. Научно-техн. журнал «Вестник ВГТУ». Воронеж: ВГТУ, 2002.

15. Бурковский В.Л., Титов С.В. Информационная система управления многопрофильным лечебным комплексом. М.: ФАП ВНТИЦ, 2002. № госрегистрации 50200200236 от 13.05.2002.

16. Бурковский В.Л. Титов С.В. Анализ применения генетических алгоритмов для решения задач планирования расписаний в СеМО. Научно-технический журнал «Системы управления и информационные технологии» № 3 (20). Воронеж: «Научная книга», 2005. - с. 33-36.

17. Бурковский В.Л., Титов С.В., Оптимизация стохастических сетей эволюционными методами поиска. Сборник научных трудов «Электротехнические комплексы и системы управления». Воронеж: ВГТУ, 2003.

18. Бурковский В.Л. Титов С.В. Эволюционный подход к планированию расписаний в сетях массового обслуживания. Материалы всероссийской научно-технической конференции «Информационные технологии 2005». -Воронеж: «Научная книга», 2005. с. 183-186.

19. Бурковский В.Д., Холопкина Л.Б., Райхель Н.Л., Кравец О.Я. Методы моделирования и анализа вычислительных систем. Воронеж: ВГТУ, 1995. -112 с.

20. Бурлаков М.В. Ситуационное управление в системах массового обслуживания. Киев: Наук, думка, 1991. - 160 с.

21. Бурлаков М.В. Определение минимальных потерь на ожидание в одноканальной системе массового обслуживания // Автоматика и телемеханика. 1984. -№ 1.-с. 81-85.

22. Бусленко В.Н. Автоматизация имитационного моделирования сложных систем. М.: Наука, 1977. - 239 с.

23. Бусленко Н.П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. М.: Наука, 1978. 210 с.

24. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. -400 с.

25. Веклеров Е.Б. Об оптимальных абсолютных динамических приоритетах в системах массового обслуживания // Изв. АН СССР. Тех. кибернетика. 1967. - № 2. - с. 87-90.

26. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и её инженерные приложения. М.: Наука, 1991. -386 с.

27. Волковинский М.И., Кабалевский А.Н. Анализ приоритетных очередей с учетом времени переключения. -М.:Энергоиздат, 1981. 168 с.

28. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы искусственные нейронные сети и проблемы виртуальной реальности. X: Основа, 1997. - 112 с.

29. Гнеденко Б.В. Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1969. 180 с.

30. Горелова Г.В., Кацко И.А. Теория вероятностей и математическая статистика в примерах и задачах с применением Excel. — Ростов на Дону: Феникс, 2005.-480 с.

31. Жожикашвили В.А. Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. -М.: Радио и связь, 1988. 191 с.

32. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. Киев: Техника, 1986. 168 с.

33. Ивченко Г.И. Теория массового обслуживания. М.: Высшая школа, 1982.-256 с.

34. Иглхарт Д.Л., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания // Под. ред. В.В.Калашникова. М.:Радио и связь, 1984.- 136 с.

35. Калашников В.В., Рачев С.Т. Математические методы построения стохастических моделей обслуживания. М.:Наука, 1988. - 310 с.

36. Каплинский А.И. и др. Моделирование и алгоритмизация слабоформализованных задач выбора наилучших вариантов систем. Воронеж: ВГТУ, 1991.- 167 с.

37. Кениг Д., Штойян Д. Методы теории массового обслуживания: Пер. с нем. // Под. ред. Г.П.Климова. М., 1981. 327 с.

38. Клейен Дж. Статистические методы в имитационном моделировании. М.: Статистика, 1978.

39. Клейнрок JI. Вычислительные системы с очередями. М.: Мир, 1979. -600 с.

40. Клейнрок JI. Теория массового обслуживания. М.: Машиностроение, 1979.-432 с.

41. Климов Г.П. Стохастические системы обслуживания. М.: Наука, 1966.-243 с.

42. Колемаев В.А., Староверов О.В. Теория вероятностей и математическая статистика. М.: Высшая школа, 1991. - 400 с.

43. Коффман Э.Г. Теория расписаний и вычислительные машины. -М.: Наука, 1984.-334 с.

44. Лившиц А.Л., Мальц Э.А. Статистическое моделирование систем массового обслуживания. М.:Сов. радио, 1978. - 247 с.

45. Новиков О.А., Петухов С.И. Прикладные вопросы теории массового обслуживания. М.: Советское радио, 1969. - 400 с.

46. Печенкин А.В. О верхней и нижней оценках средней очереди в системе с дисциплиной Шраге // Техника средств связи. Сер. Системы связи. -М., 1980. с.24-28.

47. Печенкин А.В., Соловьев А.Д., Яшков С.Ф. О системе с дисциплиной обслуживания первым требования с минимальной оставшейся длиной // Изв. АН СССР. Техн. кибернетика. 1979. - № 5. - с. 51-58.

48. Подвальный C.JL, Бурковский B.JI. Имитационное управление технологическими объектами с гибкой структурой. Воронеж: Издательство Воронежского университета, 1988. - 168 с.

49. Рыков В.В., Лемберг Э.В. Об оптимальных динамических приоритетах в однолинейных системах массового обслуживания // Изв. АН СССР. Техн. кибернетика. 1967. № 1. - с. 25-34.

50. Саати JI.T. Принятие решений. Метод анализа иерархий — М.: Радио и связь, 1993. —320 с.

51. Саати JI.T. Элементы теории массового обслуживания и ее приложения. М.: Советское радио, 1971. - 520 с.

52. Скурихин А.Н. Генетические алгоритмы / Новости искусственного интеллекта, 1995. №4. - с. 6-46.

53. Советов Б.Я. Моделирование систем. М.: Высшая школа, 2003. - 295с.

54. Таха X. А. Введение в исследование операций. М.:Мир, 1985. - 496с.

55. Фролов В.Н. Моделирование и оптимизация сложных систем. -Воронеж: ВГТУ, 1997. 151 с.

56. Шульга Ю.Н., Анохин B.C., Поляков В.Г. Моделирование диспетчерского управления подземным локомотивным транспортом на угольных шахтах // Механизация и автоматизация управления. 1969. - № 2. -с. 17-20.

57. Шульга Ю.Н. Математическая модель управления обслуживанием в сетевых системах // Кибернетика. 1977. - № l.-c. 117-125.

58. Шульга Ю.Н. Элементы теории объемных стохастических сетей массового обслуживания и ее приложения. Киев: Наук, думка, 1990. - 160 с

59. Яшков С.Ф. Анализ очередей в ЭВМ. М.: Радио и связь, 1989. - 216с.

60. Angeline, P. J. "Genetic programming: A current snapshot," in Proceedings of the Third Annual Conference on Evolutionary Programming, D. B. Fogel and W. Atmar (Eds.), Evolutionary Programming Society, 1994.

61. Angeline, P. J., Saunders, G. M. and Pollack, J. B. An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 1994. pp. 54-65.

62. Baras J.S., Ma D.J., and Makowski A.M. Competing queues with geometric service requirements and linear costs: the |ic rule is always optimal, System Control Letters, 1985. pp. 173-180.

63. Baskett F., Chandy K., Muntz R., Pallacios F. Open, closed, and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach, 1975. pp. 248-260.

64. Boxma O.J., Levy H., and Weststrate J.A. Efficient Visit Frequencies for Polling Tables: Minimization of Waiting Cost. Queueing Systems: Theory and Applications, 1991. pp. 133-162.

65. Bremermann, H.J. Optimization through evolution and recombination. Self-Organizing Systems, M.C. Yovits, G. T. Jacobi, and G.D. Goldstine (eds.), Spartan Books, Washington DC, 1962. pp. 93-106.

66. Burke P. J. The dependence of delays in tandem queues. Ann. Math. Statist. 1964. pp. 874-875.

67. Cohen J. W. The Single Server Queue. North Holland, Amsterdam, 1969.

68. Cohoon, J. P., Hegde, S. U., Martin, W. N. and Richards, D. S. Punctuated equilibria: a parallel genetic algorithm. In Grefenstette, J. J., ed., Proceedings of the Second International Conference on Genetic Algorithms, 1987. pp. 148-154.

69. Collins, R. and Jefferson, D. An artificial neural network representation for artificial organisms. In Schwefel, H. P. and Maanner, R., eds., Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 1991. pp. 269-263.

70. Cooper, R.B. Introduction To Queueing Theory. New York: North Holland, 1981.-pp 347.

71. Cox D. R., Smith W. L. Queues. Methuen, London, 1961.

72. Cox D. R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. Proc. Camb. Phil. Soc. 1955. pp. 433-441.

73. CRPC Newsletter. World-Record Traveling Salesman Problem for 3038 Cities Solved. Web Page,http://www.crpc.rice.edu/CRPC/newsletter/jan93/news.tsp.html, 1993.

74. Fogel, L. J., Owens, A. J. and Walsh, M. J. Artificial Intelligence through Simulated Evolution. New York: John Wiley, 1966.

75. Fourman, M. P. Compaction of symbolic layout using genetic algorithms. In Grefenstette, J. J., ed., Genetic Algorithms and Their Uses: Proceedings of the First International Conference on Genetic Algorithms, 1985. pp. 141-153.

76. Friedberg, R.M. A learning machine: Part I. IBM Journal of Research and Development. 2, 1958. pp. 2-13.

77. Friedberg, R.M., B. Dunham and J.H. North. A learning machine: Part 2. IBM Journal of Research and Development, 3, 1959. pp. 282-287.

78. Fullmer, B. and Miikkulainen, R. Using marker-based genetic encoding of neural networks to evolve finite-state behavior. In Proceedings of the First European Conference on Artificial Life (ECAL-91), Paris, 1991.

79. Gittins J.C. Multi-armed Bandit Allocation Indices. Wiley. New York, 1989.

80. Goldberg, D. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading: Addison-Wesley, 1989.

81. Goldberg, D. E., Deb, K., Kargupta, H. and Harik, G. Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In Proceedings of the Fifth Annual International Conference of Genetic Algorithms (ICGA-93), 1993. pp. 56-64.

82. Grefenstette, J. J. and Baker, J. E. How genetic algorithms work: a critical look at implicit parallelism. In Schaffer, J. D., ed., Proceedings of the Third International Conference on Genetic Algorithms, . Morgan Kaufmann, 1989. pp. 2027.

83. Gupta D., Gerchak Y., and Buzacott J.A. On optimal priority rules for queues with switchover costs. Working Paper. Department of Management Sciences. University of Waterloo. 1987.

84. Hajela, P. and Lin, C.-Y. Genetic search strategies in multicriterion optimal design. Structural Optimization 4, 1992. pp. 99-107.

85. Higuchi, Т., ed., Workshop on Evolvable Systems. International Joint Conference on Artificial Intelligence, pp. 27-32.

86. Hofri M., Ross K.W. On the optimal control of two queues with server setup times and its analisys. SIAM Journal of Computing, 1987. pp. 399-420.

87. Holland, J. Adaption in Natural and Artificial Systems. University of Michigan Press, 1975.

88. Jackson J. R. Networks of waiting lines. Operations Res., 1957. pp. 518—521.

89. Jaiswal, N. K. Priority Queues. Academic Press, New York, 1968.

90. Kendall D. G. Some problems in the theory of queues. J. R. Statist. Soc., 1951. pp. 151-173.

91. Kingman J. F. C. On queues in heavy traffic. J. Roy Statist. Soc. Ser. 1962. pp. 383-392.

92. Kingman J. F. C. The single server queue in heavy traffic. Proc. Cambridge Philos. Soc. 1961. pp. 902-904.

93. Kitano, H. Designing neural networks using a genetic algorithm with a graph generation system. Complex Systems 4, 1990. pp. 461-476.

94. Klimov G.P. Time sharing service systems I. Theory of Probability and Its Applications, 1974. pp. 532-551.

95. Klimov G.P. Time sharing service systems II. Theory of Probability and Its Applications, 1978. pp. 314-321.

96. Koenigsberg E. Cyclic queues. Operat. Res. Quart., 1958. pp. 22-35.

97. Koole G. Assigning a Single Server to Inhomogeneous Queues with Switching Costs. Technical Report. CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands, 1994.

98. Koza, J. R., Bennett III, F. H., Hutchings, J. L., Bade, S. L., Keane, M. A. and Andre, D. Evolving sorting networks using genetic programming and rapidly reconfigurable field-programmable gate arrays. In Higuchi, Т., ed., Workshop on

99. Evolvable Systems. International Joint Conference on Artificial Intelligence, 1997. pp. 27-32.

100. Koza, J. R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA, USA: MIT Press, 1992.

101. Miller L.W., Schrage L. The queue M/G/l with the shortest remaining processing time discipline // Operat. Res. 1966. - 14, N 4. - pp. 670-684.

102. Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, 1996.

103. Nain P. Interchange arguments for classical scheduling problems in queues. Systems Control Letters, 1989. pp. 177-184.

104. Prabhu N. U. Queues and Inventories: A Study of Their Basic Stochastic Processes. Wiley, New York, 1965.

105. Ray, T. An approach to the synthesis of life. In Artificial Life II, C. Langton, C. Taylor, J. Farmer and S. Rasmussen (eds.), Reading, MA: Addison-Wesley Publishing Company, Inc., 1992. pp. 371-408.

106. Reeves, C.R. Using Genetic Algorithms with Small Populations. In Proceedings of the Fifth International Conference on Genetic Algorithms, 1993. pp. 92-99.

107. Reich E. Waiting times when queues are in tandem. Ann. Math. Statist, 1957. pp. 768-773.

108. Reiman M.I., Wein L.M. Dynamic Scheduling of a Two-Class Queue with Setups. Technical Report. Sloan School of Management. M.I.T., Cambridge, MA 02139. 1994

109. Schrage L. A proof of optimality of the shortest remaining processing time discipline // Operat. Res. 1968. - 16, N 3. - pp. 687-690.

110. Schwefel, H.P. Numerische Optimierung vonComputer-Modellen mittels der Evolutionsstrategie ("Numeric Optimization of Computer Models by Means of an Evolution Strategy"), Interdisciplinary System Research, Volume 26. Bassel: Birkhauser, 1977.

111. Walrand J. An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, 1988.

112. Wilson, P. B. and Macleod, M. D. Low implementation cost IIR digital filter design using genetic algorithms. In IEE/IEEE Workshop on Natural Algorithms in Signal Processing, Volume 4, 1993. pp. 1-8.

113. Wright, S. Stochastic processes in evolution. In Gurland, J., ed., Stochastic Models in Medicine and Biology, 1964. pp. 199-241. University of Wisconsin Press.

114. Whitley, D. The GENITOR algorithm and selection pressure: why ranked-based allocation of reproductive trials is best. In Schaffer, J. D., ed., Proceedings of the Third International Conference on Genetic Algorithms, 1989. pp. 239-255. Morgan Kaufmann.