Компьютерное моделирование процессов в системах и сетях массового обслуживания

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

ЗАХАРИКОВА Елена Борисовна

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

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

Автореферат

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

кандидата технических наук

ПЕНЗА 2013

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

Защита диссертации состоится 14 марта 2013 г., в 14 часов, на заседании диссертационного совета Д 212.186.04 в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Пензенский государ­ственный университет» по адресу: 440026,
г. Пенза, ул. Красная, 40.

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

Автореферат разослан 11 февраля 2013 г.

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

диссертационного совета Косников Юрий Николаевич

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

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

Значительный вклад в развитие математических и имитационных методов моделирования внесли А. А. Марков, А. Н. Колмогоров, А. Я. Хинчин,
Л. Клейнрок, Р. Шеннон, Т. Саати, Л. А. Овчаров, Е. С. Вентцель, Б. В. Гнеденко, И. Н. Коваленко, Н. П. Бусленко, В. Е. Котов, Дж. Питерсон, В. Кельтон,
А. Лоу, А. А. Самарский, Э. К. Алгазинов, Т. И. Алиев, П. П. Макарычев и др.

В настоящее время для имитационного моделирования разработаны специализированные проблемно-ориентированные программные средства Arena, AnyLogic, GPSS, Vissim, ExtendSim, AutoMod, Promodel и др., к недостаткам ко­торых можно отнести сравнительно высокую стоимость и требование достаточ­но высокого уровня подготовки персонала; а также универсальные математические пакеты Mathcad, Matlab, Maple, Mathematica, Scilab, Maxima, FreeMat и др.

К достоинствам математических пакетов следует отнести наличие простого и удобного интерфейса, библиотеки встроенных функций, графических средств представления результатов, возможность символьных вычислений, а так­же возможность интеграции с множеством специализированных программ­ных про­дуктов. Кроме того, математические пакеты являются инструментальными средствами, позволяющими реализовать как численное, так и имитационное моделирование систем. В математическом пакете Mathcad имеется возможность взаимодействия со следующими программными продуктами: приложени­ем для моделирования систем на сигнальном или физическом уровне VisSim/Comm PE, программными комплексами САПР Pro/ENGINEER, Solid­Works, AutoCAD, чертежным приложением SmartSketch, табличным процессором Exсel, математическим пакетом Matlab. Открытая архитектура приложения в сочетании с поддер­ж­­кой технологий NET, HTML и XML позволяет лег­ко интегрировать Mathcad практически в любые IT-структуры и инженерные приложения. Поддер­живаются стандартные языки программирования сценариев, такие как VBScript и JScript. Имеется возможность создания электрон­ных книг (e-Book).

Однако моделирование достаточно сложных систем и сетей массового обслуживания средствами математических пакетов занимает значительно больше времени по сравнению с использованием универсальных языков программирования. Это обусловлено тем, что встроенные в математические пакеты языки программирования являются интерпретируемыми, а универсальные, такие как C++, Pascal, Java, Basic, – компилируемыми. Помимо этого, при разработке имитационных моделей в среде математических пакетов отсутствует возможность скрытия исходного кода и создания достаточно удобного интерфейса.

Для объединения достоинств математических пакетов и универсальных языков программирования в математические пакеты встроен инструмент подключения внешних модулей, написанных на языке С++. Математическая система Mathcad имеет многофункциональное ядро, однако прямой доступ к большинству операций ядра для пользователей закрыт. Для расширения функциональных возможностей в системе Mathcad содержится инструмент, позволяющий пе­ревести пользовательские функции, написанные на языке С++, в разряд встроенных через механизм DLL (Dynamic Link Library). Сами функции, созданные через механизм DLL, имеют универсальный характер и мо­гут подключаться к другим расчетным и программным средам (Matlab, Mathematica, Scilab, FreeMat). Mathcad поставляется с дополнительными библиотеками, предназначенными для анализа данных, обработки сигналов и изображений, волнового преобразования, пакетами строительства, электротехники и машиностроения. Основная проблема, связанная с подключением внешних модулей, заключается в том, что в среде Mathcad не предусмотрена библиотека для проведения имитационного моделирования, в связи с чем отсутствует алгоритм построения математической модели для организации имитационного моделирования систем и сетей массового обслуживания. Таким образом, задача разработки комплекса прикладных про­г­рамм имитационного моделирования, который может быть встроен в Mathcad, а также в другие математические пакеты, является актуальной.

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

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

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

Для достижения поставленной цели решены следующие задачи:

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

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

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

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

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

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

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

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

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

4) разработан алгоритм расчета узловых характеристик имитационной модели сети массового обслуживания, который отличается оценкой распределения вероятностей состояний, что позволяет провести сравнительный ана­лиз результатов имитационного моделирования с решениями системы уравнений Кол­могорова и оценить степень адекватности имитационной модели;

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

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

Достоверность результатов работы основана на результатах проведенных исследований:

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

исследование имитационных моделей узлов обслуживания на адекватность, чувствительность и устойчивость;

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Комплекс программ имитационного моделирования и практические результаты внедрены в ОАО «Научно-производственное предприятие “Рубин”».

Материалы диссертационной работы использованы при проведении лабо­раторных занятий по дисциплинам «Теория массового обслуживания», «Ком­­пью­терное моделирование», изучаемым студентами специальности 230105.65 –
«Программное обеспечение вычислительной техники и автоматизированных си­стем» факультета вычислительной техники ПГУ.

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях: V (юбилейной) Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2011 г.); V Международной научно-технической конференции молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (Пенза, 2011 г.); Международной научно-практической конференции «Молодежь и наука: модернизация и инновационное развитие страны» (Пенза, 2011 г.); V Всероссийской молодежной научной конференции «Мавлютовские чтения» (Уфа, 2011 г.); XVI Международной научно-методической конференции «Университетское образование» (Пенза, 2012 г.); Международной молодежной конференции в рамках фестиваля науки «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012 г.); XII Международной заочной научно-практической конференции «Инновации в науке» (Новосибирск, 2012 г.); VIII Международной научно-прак­тической конференции «Со­временное состояние естественных и технических наук»
(Моск­ва, 2012 г.).

Публикации. По теме диссертационного исследования опубликовано
11 печатных работ: 3 статьи в изданиях из перечня ВАК, 8 – в других из-даниях.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 145 наименований и трех приложений. Объем работы: 172 страницы основного текста, включающего 87 рисунков, 27 таблиц и 51 страницу приложений.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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