Содержание к диссертации
Введение
Глава 1. Сети массового обслуживания и эволюционные методы поиска оптимальных решений 12
1.1. Состояние и тенденции развития теории массового обслуживания 12
1.2. Анализ эволюционных методов поиска оптимальных решений 23
1.3. Постановка задачи выбора оптимальных решений на основе моделей массового обслуживания
39
Цель работы и задачи исследования 41
Выводы 43
Глава 2. Агентное имитационное моделирование сетей массового обслуживания 44
2.1. Технология агентного имитационного моделирования 45
2.2. Алгоритмы имитационного моделирования 51
2.3. Статистическая обработка результатов моделирования 59
Выводы 63
Глава 3. Оптимизация семо на основе эволюционных методов 64
3.1. Выбор критерия оптимальности 66
3.2. Разработка способа кодирования хромосомы 70
3.3. Вычисление минимального размера популяции 72
3.4. Разработка генетических операторов 75
3.5. Поколенческий генетический алгоритм 77
3.6. Подбор параметров генетического алгоритма 81
Выводы 86
Глава 4. Программное обеспечение моделирования и оптимизации сетей массового обслуживания 87
4.1. Структура программного комплекса моделирования и оптимизации 87
4.2. Объектно-ориентированное представление модели 89
4.3. Модуль графического редактирования модели 96
4.4. Графический интерфейс пользователя 102
4.5. Анализ результатов моделирования 116
Выводы 121
Глава 5. Результаты практической аппробации алгоритмов моделирования и оптимизации семо 123
5.1. Имитационное моделирование семо на примере медико-санитарной части оао «сгок» 123
5.2. Выбор оптимальных стратегий обслуживания материало-потоков зерноперерабатывающего
Комбината 128
Заключение 138
Литература
- Постановка задачи выбора оптимальных решений на основе моделей массового обслуживания
- Алгоритмы имитационного моделирования
- Вычисление минимального размера популяции
- Модуль графического редактирования модели
Введение к работе
АКТУАЛЬНОСТЬ ТЕМЫ
Высокая практическая актуальность вопросов совершенствования методов
и алгоритмов принятия решений в рамках систем управления объектами
производственных и непромышленных отраслей, а также наличие в этой
области значительного числа трудноформализуемых факторов требует для их
решения применения современных математических методов и программных
систем. Среди множества объектов управления следует выделить класс сетей
массового обслуживания, функционирующих в условиях
сложноструктурированных информационных и материальных потоков. К таким объектам можно отнести транспортные сети, вычислительные сети, сетевые технологические системы, сетевые медицинские системы. Использование в данной области строгих математических моделей и методов ограничено наличием большого числа неконтролируемых источников внешних и внутренних возмущений. Альтернативой аналитическому аппарату анализа здесь являются средства имитационного моделирования. Кроме того, большое количество управляющих параметров и альтернативных структур в рамках таких систем делает актуальным использование эволюционных методов для оптимального управления сетями массового обслуживания.
Таким образом, актуальность темы диссертационной работы продиктована необходимостью дальнейшего развития формализованных средств аппарата моделирования, анализа и оптимизации сетей массового обслуживания с целью повышения эффективности их функционирования.
Тема диссертационной работы соответствует одному из научных направлений Воронежского государственного технического университета «Вычислительные системы и программно-аппаратные комплексы».
ЦЕЛЬ РАБОТЫ
Целью работы является разработка средств формализованного описания процессов функционирования сетей массового обслуживания, составляющих содержательную основу комплексной имитационной системы анализа, а также моделей и алгоритмов оптимального принятия решений на основе эволюционных методов.
Исходя из данной цели, в работе определены следующие задачи исследования:
разработка формализованного описания процессов взаимодействия неоднородных потоков заявок в сетях массового обслуживания;
разработка комплексной имитационной модели анализа процессов функционирования сетей массового обслуживания, реализующей средства адаптации к специфическим особенностям объектной среды;
разработка моделей оптимального выбора структур потоков заявок, базирующихся на эволюционных методах, для чего осуществить:
разработку схемы кодирования хромосом возможных решений, функций перехода из пространства представлений в пространство объектов;
разработку генетических операторов скрещивания и мутации применительно к выбранной схеме кодирования хромосомы;
анализ вариантов параметров генетического алгоритма и выбор наилучших;
разработка графической среды построения моделей, визуализирующей структуру исследуемой системы и взаимодействие входящих в нее подсистем;
разработка программного обеспечения имитационного моделирования, анализа и оптимального управления сетями массового обслуживания.
7 МЕТОДЫ ИССЛЕДОВАНИЯ
Методы исследования основаны на использовании теории массового обслуживания, эволюционных методов, теории вероятностей, дискретной математики, теории графов, вычислительной математики, объектно-ориентированного программирования, компьютерных технологий.
НАУЧНАЯ НОВИЗНА
В работе получены следующие результаты, характеризующиеся научной новизной:
формализованное описание процессов взаимодействия неоднородных потоков заявок в сетях массового обслуживания, отличающееся возможностью реструктуризации в условиях воздействия неконтролируемых источников возмущений;
комплексная имитационная модель процессов функционирования сетей массового обслуживания, позволяющая осуществлять оперативную адаптацию модулей моделирования к специфическим особенностям конкретной объектной области;
модель принятия решений по оптимальной реструктуризации потоков заявок, отличающаяся реализацией эволюционных методов; специальные схемы кодирования хромосом и обусловленные методом кодирования генетические операторы, а также детерминированный подход к применению оператора мутации и выборочный способ инициализации начальной популяции, повышающие сходимость алгоритма поиска оптимальных решений;
подсистема графического изображения и редактирования моделей СеМО, обеспечивающая высокую производительность оператора;
программное обеспечение моделирования, анализа и принятия решений, отличающееся специальной структурой организации содержательных компонент.
8 ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ
В работе предложен комплекс моделей, алгоритмов и программных средств, позволяющий произвести имитационное моделирование и оптимизацию сетей массового обслуживания в различных объектных областях.
Использование данного комплекса в контуре управления производственными, транспортными, вычислительными системами, а также системами непромышленной сферы обеспечивает поиск потенциальных «узких мест» в модели, определение запаса производительности, оптимальное использование имеющихся ресурсов, а также принятие рациональных управленческих решений по проведению реструктуризации с целью повышения качества функционирования систем.
РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ
Основные теоретические и практические результаты работы реализованы в виде программного обеспечения, позволяющего осуществить моделирование, оперативный анализ и оптимальное управление сетями массового обслуживания в различных объектных областях. Результаты работы использованы в ОАО «Елецкий крупяной завод».
Ожидаемый годовой экономический эффект, полученный при внедрении результатов диссертации в ОАО «Елецкий крупяной завод», составляет 523 тыс. руб. в ценах 2005 года. Эффект достигается за счет уменьшения времени простоя производственных линий, уменьшения объема отложенного обслуживания, увеличения объема переработки наиболее приоритетных типов сырья.
Кроме того, теоретические результаты исследования используются в учебном процессе кафедры «Автоматика и информатика в технических системах» в дисциплинах «Моделирование систем управления», «Диагностика и идентификация систем управления».
АПРОБАЦИЯ РАБОТЫ
Основные результаты докладывались и обсуждались на международной научно-практической конференции «Теория активных систем» (Москва, 2001);
VI Международной открытой научной конференции «Современные проблемы
информатизации в технике и технологиях» (Воронеж, 2001); региональной научно-технической конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2002-2003); международной конференции СССУ/HTCS 2003 «Современные сложные системы управления», всероссийской научно-технической конференции «Информационные технологии» (Воронеж, 2005), а также на научных семинарах кафедры автоматизированных и вычислительных систем.
ПУБЛИКАЦИИ
По результатам исследований опубликовано 14 научных работ. В работах, опубликованных в соавторстве и приведенных в конце диссертации, лично соискателем предложены: в работе [4] - формализованное описание процессов взаимодействия неоднородных потоков заявок в сетевых системах массового обслуживания; в [17,21] - подход к имитационному моделированию сетевых систем со сложным поведением заявок; в [19,20,22,23,24] - эволюционный подход к задаче оптимального управления СеМО; в [15,16,18,61] -программное обеспечение моделирования, анализа и оптимального управления сетями массового обслуживания; в [2,3] - практическая применимость комплексной имитационной системы моделирования и анализа.
СТРУКТУРА И ОБЪЕМ РАБОТЫ
Диссертация состоит из введения, пяти глав, заключения, списка литературы из 127 наименований и трех приложений на 14 страницах. Основная часть работы изложена на 138 страницах, содержит 54 рисунка и 22 таблицы.
СОДЕРЖАНИЕ РАБОТЫ
В первой главе проводится анализ тенденций развития теории массового обслуживания. Рассмотрены методы ситуационного управления сетями массового обслуживания с переключением. Сделан вывод о необходимости оптимизации сетей массового обслуживания с точки зрения обеспечения качества функционирования. Рассмотрены эволюционные методы поиска
10 оптимальных решений, проведена классификация эволюционных методов по способу кодирования хромосом и применению основных генетических операторов. Обосновано использование эволюционных методов для принятия управленческих решений в сетях массового обслуживания.
Во второй главе предлагается агентный подход к задаче имитационного моделирования СеМО. Рассмотрена технология агентного имитационного моделирования применительно к поставленной задаче. Описаны агенты модели и схема их взаимодействия. В рамках предложенного агентного подхода разработаны алгоритмы имитационного моделирования. С целью повышения эффективности статистической обработки результатов моделирования предложены методы получения наблюдений, уменьшающие автокорреляцию, методы понижения дисперсии, рассматривается способ вычисления окончания переходного процесса, затронуты вопросы обеспечения требуемого уровня точности моделирования.
Третья глава посвящена решению задачи оптимального управления сетями массового обслуживания на основе эволюционных методов. Рассматривается решение проблемы поиска эффективных расписаний переключения обслуживающих приборов между несколькими классами заявок в условиях наличия временных затрат на переключения. Разрабатываются: специальная схема кодирования хромосом возможных решений, генетические операторы скрещивания и мутации. Предложен способ инициализации начальной популяции хорошими решениями, в отличие от традиционной случайной инициализации. Для предотвращения преждевременной сходимости к локальному экстремуму предлагается детерминированный подход к применению оператора мутации. Проведены тестовые испытания, сравнивающие детерминированное и вероятностное применение оператора мутации.
В четвертой главе описывается программное обеспечение моделирования, анализа и оптимального управления сетями массового обслуживания. Разработанное программное обеспечение позволяет отображать и формировать в графическом виде структуру сети массового обслуживания, редактировать
параметры ее элементов, осуществлять имитационное моделирование системы, осуществлять поиск эффективных графиков перенастройки обслуживающих приборов между различными классами заявок с учетом временных затрат на переключение. По результатами имитационного моделирования создаются отчеты со статистической информацией представленной в виде графиков и диаграмм (с возможностью распечатки на принтере). Предусмотрена возможность сохранение сформированной модели в файл и чтения из файла. Рассмотрена архитектура системы, объектно-ориентированные структуры данных, дается описание модуля графического редактирования модели, приведено руководство пользователя с описанием интерфейса разработанного программного обеспечения.
В пятой главе обсуждаются результаты использования предложенных методов, алгоритмов и программных средств на реальных системах при практическом моделировании медико-санитарной части открытого акционерного общества «Стойленский горно-обогатительный комбинат» и оптимизации ОАО «Елецкий крупяной завод».
В заключении формулируются научные и практические результаты диссертационного исследования.
В приложениях приводятся результаты имитационного моделирования медико-санитарной части открытого акционерного общества «Стойленский горно-обогатительный комбинат» и результаты имитационного моделирования ОАО «Елецкий крупяной завод» до и после оптимизации.
Постановка задачи выбора оптимальных решений на основе моделей массового обслуживания
Рассмотрим задачу определения характеристик функционирования разомкнутой сети массового обслуживания в стационарном режиме, состоящей из R узлов, между которыми циркулируют требования Q различных типов, каждый тип имеет приоритет dj, (1 j Q); z-й узел (1 і R ) содержит mi параллельных каналов обслуживания. Перед каждым прибором обслуживания располагается очередь с количеством мест для ожидания /,. Дисциплина постановки в очередь FIFO, реализует процедуру абсолютных приоритетов, при которой заявка с большим приоритетом помещается перед заявкой с меньшим приоритетом. Время обслуживания всех типов заявок любым прибором z -го узла может иметь произвольное распределение (в программной реализации предусмотреть равномерное, показательное и экспоненциальное). Схема взаимодействия отдельных узлов сети задана полносвязанным графом, каждая Rt -я вершина которого связана с вершиной Rj посредством ребра s . В сеть поступают Q произвольных потоков требований. Обычно маршрут требований в сети массового обслуживания с несколькими классами задается матрицей: Р = А Д, (1.6) где Р\г,к - вероятность того, что требование г-го класса, закончившее обслуживание в z -м узле, перейдет в к-й узел.
Специфика же исследуемой системы заключается в том, что маршрут заявок каждого типа определяется необходимостью посетить с некоторой вероятностью определенное множество обслуживающих приборов, состав этого множества и значения вероятностей посещения обслуживающих приборов обусловлены типом заявки. Таким образом, задана следующая матрица: Р 1,1 Р 2,1 Рт,1 P l,2 Р 2,2 Р т,2 (1 VP l,n Р 2,п Р т,пУ где p\j - вероятность того, что поступившая в систему заявка /-го типа, посетит обслуживающий прибор с номером у . Для описанной сети массового обслуживания необходимо разработать технологию имитационного моделирования, позволяющую найти следующие параметры функционирования в стационарном режиме: процентное соотношение обслуженных и необслуженных заявок всего и по типам заявок; процентное соотношение времени работы и простоя каждого обслуживающего прибора и его каналов. средние и максимальные длины очередей; среднее время обслуживания заявок /-го типа (\ i Q); среднее время ожидания заявок /-го типа {\ і Q);
Базируясь на созданной в рамках решения первой задачи системе имитационного моделирования и анализа, для описанной ниже сети массового обслуживания необходимо решить задачу поиска графика перенастройки обслуживающих приборов между классами заявок, максимизирующего критерий эффективности функционирования сети. При этом необходимо учитывать временные затраты, затрачиваемые на перенастройку обслуживающих приборов.
Оптимизируемая СеМО отличается от описанной выше схемой взаимодействия отдельных узлов сети. Она состоит из R параллельных не связанных друг с другом приборов обслуживания. Перед каждым прибором обслуживания расположена очередь с ограниченным количеством мест для ожидания /,. В сети циркулируют заявки Q различных типов с независимыми входными потоками. После появления в системе заявки поступают во входную групповую очередь, откуда в дальнейшем распределяются в любой из свободных обслуживающих приборов или становятся в очередь перед прибором, если он занят. В каждый момент времени обслуживающий прибор может обрабатывать заявки только одного из Q типов, поэтому из входной очереди заявки /-го класса могут поступать только в те обслуживающие приборы, которые в момент диспетчеризации настроены на обработку /-го класса.
Существует возможность переключения обслуживающего прибора между заявками различных типов, что требует определенных временных затрат. Для каждого прибора задана следующая матрица перенастройки: ( 0 t t \ v м,2 м,д 2J - h Q , (1.8) где tj. j - время, затрачиваемое на переключения обслуживающего прибора с заявок г -го типа на обработку заявоку-го типа; Q - количество типов заявок.
В качестве метода поиска графика перенастройки обслуживающих приборов между классами заявок будем использовать генетические алгоритмы, для адаптации которых к предметной области необходимо осуществить разработку схемы кодирования хромосом возможных решений, процедур перехода из пространства представлений в пространство объектов, осуществить подбор наилучших параметров генетического алгоритма, создать генетические операторы отбора, скрещивания и мутации применительно к выбранной схеме кодирования хромосом.
Алгоритмы имитационного моделирования
Процедура имитационного моделирования основана на обработке представления модели в виде ориентированного графа и представляет собой цикл по времени моделирования. На каждом шаге цикла нам известно текущее время, обозначаемое в программе как СигТіте. В зависимости от текущего времени, в модели происходят различные события, такие как поступление новой заявки из входного потока, окончания обработки заявки в обслуживающем прибора, поступление заявки на обработку в обслуживающий прибор или на ожидание в очередь, выход заявки из системы и классификация ее как обслуженной или необслуженной. Эти события последовательно обрабатываются и тем самым меняют текущее состояние системы, а именно: количество поступивших и выбывших заявок, длину очередей и их состав, загрузку обслуживающих приборов. Рассмотрим подробно основной алгоритм имитационного моделирования.
Процесс моделирования запускается процедурой StartModeling, которая состоит из следующих этапов:
1) Инициализируем все структуры данных, хранящие информацию о состоянии модели во время моделирования. Обнуляем счетчик времени и количество поступивших и покинувших систему заявок.
2) Генерируем первые заявки, т. е. определяем время поступления первой заявки из каждой группы, в зависимости от функций распределения входных потоков.
3) Перебираем все обслуживающие приборы и все каналы, имеющиеся у них. Если время окончания обслуживания заявки совпадает с текущим, то маршрутизируем заявку дальше в соответствии с присоединенными к прибору связями и обнуляем время окончания обработки заявки в данном канале.
4) Перебираем вначале все групповые очереди, а затем все обычные. Берем заявку, которая поступила в очередь раньше всех, если процедура функционирования очереди - строгое FIFO, либо перебираем все заявки, начиная с поступившей ранее всего, в противном случае. Пытаемся маршрутизировать заявку в какой-либо обслуживающий прибор либо очередь, присоединенную к данной. Если попытка удается, тогда сдвигаем все заявки к началу очереди и уменьшаем ее длину.
5) Перебираем все группы заявок. Если время поступления заявки совпадает с текущим, тогда добавляем заявку в динамический массив, маршрутизируем заявку, увеличиваем счетчик поступивших заявок. Если мы еще не достигли заданного количества заявок или времени окончания генерации заявок, то определяем время поступления следующей заявки данного типа. 6) Собираем статистику по занятости обслуживающих приборов и длине очередей. 7) Увеличение счетчика времени на единицу. 8) Если моделирование завершается по наступлению заданного времени, то проверка текущего времени на равенство с заданным; если условием окончания моделирования является поступление и обслуживание заданного количества заявок, то проверка количества выбывших из системы заявок на равенство с заданным. Если соответствующее условие оказалось истинным, выполняем освобождение занятой памяти и возвращаем управление из процедуры.
9) Возвращаемся к пункту 3.
Основные этапы алгоритма моделирования представлены на рис. 2.2. Процедура маршрутизации заявки согласно особенностям объектно-ориентированного языка программирования реализована в виде методов объектов: TIn.OutDemand (для входного потока), TApparat.OutDemand (для обслуживающего прибора), TQueue.OutDemand (для очереди). Для заявок, находящихся в очередях, метод возвращает, смогла ли заявка покинуть очередь.
Алгоритм методов зависит от того, где находится заявка:
1) Заявка находится во входном потоке. Суммируются значения относительных вероятностей связей, выходящих из входного потока. Если сумма равна нулю, генерируется ошибка, в противном случае выбирается связь. Совершается попытка поместить заявку в элемент, присоединенный к концу связи. Если попытка не удалась, заявка считается не обслуженной и выбывает из модели.
2) Заявка находится в обслуживающем приборе. Суммируются значения относительных вероятностей связей, выходящих из него. Если сумма равна нулю, проверяется принадлежность заявки групповой очереди. Если заявка принадлежит групповой очереди, осуществляется попытка поместить заявку в эту групповую очередь, если попытка не удалась, заявка считается необслуженной и выбывает из модели. Если сумма равна нулю и заявка не принадлежит к групповой очереди, она считается полностью обслуженной заявкой и выбывает из модели. Если сумма не равна нулю, выбирается связь. Совершается попытка поместить заявку в элемент, присоединенный к концу связи. Если попытка не удалась, заявка считается не обслуженной и выбывает из модели.
Вычисление минимального размера популяции
Эффективность генетического алгоритма в большой степени зависит от рационального подбора управляющих параметров, таких как: размер популяции, критерий окончания эволюционного процесса, метод отбора, оператор скрещивания, вероятность скрещивания, вероятность мутации, применяется ли стратегия элитизма и сколько элитных особей используется.
Чаще всего применяемые значения параметров сведены в таблицу 3.1. Однако использование стандартных значений может привести к значительным потерям в эффективности алгоритма. Для вычисления оптимальных значений параметров проводились исследования на специально сгенерированных тестовых задачах, а также в различных предметных областях. Но универсальных методов в настоящее время не разработано, и для каждой новой задачи приходится методом проб и ошибок подбирать эффективный набор управляющих параметров.
В настоящей работе размер популяции определяется исходя из структуры оптимизируемой сети массового обслуживания. Количество временных отрезков на интервале моделирования определяет длину строки хромосомы. Количество возможных процедур перенастройки задает арность алфавита. Используя эти данные, по рис. 3.6 можно определить минимально допустимый размер популяции, который позволит достаточно полно охватить пространство поиска.
Вместо того, чтобы выбирать перед запуском алгоритма количество поколений, на протяжении которых осуществляется поиск лучшего решения, будем использовать следующий критерий останова: если на протяжении последних N поколений (N принимаем равным 100) приспособленность лучшего индивида не увеличилась, процесс завершен. Отсутствие роста приспособленности лучшего индивида указывает на то, что решения сгруппировались в области локального или глобального экстремума, что позволяет принять решение об останове алгоритма.
Пропорциональный отбор обладает рядом недостатков, в частности, если абсолютные значения приспособленности велики, а разность между ними незначительна, то следующее поколение будет формироваться практически случайным образом. Поэтому, для селекции индивидов будем использовать турнирный отбор, при котором из двух случайно выбранных индивидов в следующее поколение переходит наилучший.
Длительность оценки приспособленности индивида, определяемая процедурой имитационного моделирования, а также обусловленный этим небольшой размер используемых популяций оказывают влияние на способы применения операторов скрещивания и мутации. Обычно, значение вероятности кроссовера лежит в интервале 0,6-0,9. Оно выбирается чуть меньше единицы для того, чтобы в небольшом количестве случаев оба родителя перешли в следующее поколение без изменений. Однако, стремясь минимизировать количество вычислений целевой функции, мы заинтересованы в том, чтобы приспособленность росла от поколения к поколению большими темпами. К тому же используемая стратегия элитизма обеспечит переход нескольких лучших особей в следующее поколение без изменений. Поэтому будем применять оператор скрещивания с вероятностью 1,0.
В отличие от используемого стандартного подхода, когда мутация применяется с небольшой вероятностью, обычно выбираемую в пределах 0,001 - 0,01, будем применять мутацию в случае, если для скрещивания были выбраны два идентичных индивида. Как уже было отмечено в параграфе 3.4, , это предотвращает вырождение популяции, увеличивает генетическое разнообразие и, таким образом, способствует большему охвату пространства поиска.
Для того, чтобы оценить насколько эффективен такой метод применения оператора мутации, были проведены испытания на двух тестовых задачах разной размерности с известными лучшими решениями. Для наглядности результатов эволюционный процесс не был остановлен при прекращении роста приспособленности лучшей особи, а продолжался вплоть до достижения поколения 1000. Во всех тестах использовались поколения из 20 индивидов, турнирный отбор, 1 элитная особь, вероятность скрещивания 1,0.
Для 1-й тестовой задачи на рис. 3.10а в виде поверхности приспособленности изображены результаты работы алгоритма, применявшего мутацию с вероятностью 0,01. Каждые 50 поколений проводились измерения приспособленности всех 20 индивидов и в отсортированном виде откладывались вдоль оси, промаркированной от 1 до 20, формируя таким образом, ландшафт эволюционного процесса. На рис. 3.1 Об показаны графики роста приспособленности среднего, худшего и лучшего индивида. На рис. 3.11 изображены аналогичные показатели результатов работы 2-го алгоритма, применявшего оператор мутации, если для скрещивания вдруг будут выбраны два идентичных индивида.
Модуль графического редактирования модели
В структуре СеМО присутствует большое количество обслуживающих приборов, как одноканальных, так и многоканальных; перед ними может организовываться как однородная, так и структурированная по типам заявок очередь. Поэтому задача формирования пользователем структуры модели и ввода параметров ее элементов является нетривиальной. Соответствующий пользовательский интерфейс должен предоставлять возможность удобной навигации по списку элементов модели, поиска определенного элемента, корректировки параметров каждого элемента. Необходимо предоставить пользователю возможность наглядного представления структуры модели и взаимосвязей между ее элементами.
Возможны два способа представления исходных данных для моделирования: табличный, либо графический вариант изображения модели. Хотя реализация табличного варианта проще в нескольких аспектах, она имеет ряд недостатков: меньшая наглядность, чем у графического; сложность задания моделей, со структурой потоков заявок отличных от стандартных: параллельных, последовательных и так далее. Графическое представление модели дает свободу при указании потоков заявок любой конфигурации и позволяет легко увидеть модель в целом и найти ошибки при задании связей между очередями и обслуживающими приборами. Несмотря на то, что программная реализация графического представления модели значительно сложнее, чем табличного, и представляет собой по существу небольшую систему САПР, предпочтение было отдано этому варианту.
Основой проектирования графического редактора является представление структуры модели в виде ориентированного графа. Узлами этого графа являются: входной поток, очереди, обслуживающие приборы. Ребра графа 97 связи между перечисленными элементами, которые отражают маршруты потоков заявок в системе.
В графическом редакторе различные объекты модели, а именно: входной поток, очередь и обслуживающий прибор - представлены в виде различных пиктограмм, соответствующих типу элемента. Пиктограммы очередей и обслуживающих приборов имеют справа выход для обслуженных заявок (плюс), а сверху - выход для необслуженных заявок (минус): в случае групповых очередей - это выход для заявок, посетивших все обслуживающие приборы, присоединенные к данной очереди. Связи, отражающие перемещение потоков заявок будем изображать в виде линий со стрелками от одного элемента модели к другому. Для манипулирования элементами модели введем понятие текущий (выделенный) элемент - это элемент, с которым, в зависимости от его типа, можно производить различные операции (удалять, перемещать, копировать, вызывать окно его параметров для редактирования и т.д.). Рамка вокруг пиктограммы текущего элемента, знаки «плюс» и «минус», а также отображаемое под элементом название рисуются красным цветом. В соответствии с этими требованиями реализован алгоритм функционирования графической подсистемы, упрощенная схема которого представлена на рис. 4.2.
Функционирование подсистемы графического изображения и корректировки модели базируется на четырех сообщениях, поступающих из ядра операционной системы Windows:
OnPaint. Инициализируется операционной системой, когда необходимо перерисовать экран. Процедура вызывает подпрограмму DrawObj для каждого объекта системы. Сначала рисуются связи, чтобы они оказались на заднем плане в случае пересечения с другими объектами модели. Схема алгоритма процедуры перерисовки экрана изображена на рис. 4.3.
OnMouseDown. Инициализируется операционной системой, когда пользователь нажимает кнопку мыши. Выполняются различные действия, в зависимости от состояния графического редактора (выделение элемента, вставка обслуживающего прибора, вставка линии, вставка связи). OnMouseMove. Инициализируется системой, когда пользователь перемещает мышь или устройство позиционирования. OnMouseUp. Инициализируется системой, когда пользователь отпускает кнопку мыши.
Модуль UDraw, в котором находится подсистема графического изображения и корректировки модели, содержит обработчики сообщений операционной системы Windows, а также следующие вспомогательные процедуры:
FormCreate. Процедура вызывается при загрузке и создании основного окна программы. В ней инициализируется графическая подсистема, загружаются в память из ресурса приложения растровые изображения элементов модели, создается вариант модели, заданный по умолчанию.
DrawObj(obj : TDrawObj; plus, minus : boolean). Процедура вызывается для прорисовки элемента модели obj. Параметры plus, minus определяют, будут ли знаки (+) и (-) в изображаемом объекте выделенными. Схема процедуры прорисовки элемента модели изображена на рис. 4.4.
DгаwOldSelected. Процедура вызывается для того, чтобы перерисовать предыдущий выделенный объект обычным цветом.
ClearDrag. Сбрасывает в начальное состояние значения переменных, которые были задействованы при перемещении объекта.
SelectedChanged. Процедура вызывается при смене выделенного элемента. В зависимости от типа нового текущего элемента устанавливается или сбрасывается свойство доступности пользователю у кнопок панели инструментов, таких как «удалить», «вырезать», «скопировать с буфер», «вставить из буфера», «отобразить окно параметров элемента», реализующих соответствующие действия с выделенным элементом.
