Компьютерное моделирование процессов в системах и сетях массового обслуживания
На правах рукописи
ЗАХАРИКОВА Елена Борисовна
КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ
В СИСТЕМАХ И СЕТЯХ МАССОВОГО ОБСЛУЖИВАНИЯ
Специальность 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, SolidWorks, 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 также реализованы эффективные методы для проведения численного моделирования, которые основаны на аппроксимации дифференциальных уравнений разностными аналогами (метод Рунге-Кутта с фиксированным, переменным шагом, метод Булирша-Штера). Однако эти методы применяются только для моделирования СМО.