Содержание к диссертации
Введение
Глава 1. Обзор современного состояния проблемы 10
1.1 Дискретное описание объектов различной природы 10
1.2 Имитационное моделирование 15
1.3 Формальные методы поиска требуемых конфигураций ДО 20
1.4 Интеллектуальные методы поиска конфигурации 24
1.5 Средства поиска конфигураций с заданным поведение 26
1.6 Генетические алгоритмы 27
1.7 Сети Петри как средства имитационного моделирования ДО 33
1.8 Постановка задачи 44
Глава 2. Имитационная модель формирования конфигурации ДО со статической структурой 46
2.1 Формальная постановка задачи 46
2.2 Описание генотипа сетями Петри 49
2.3 Целевая функция 51
2.4 Описание операторов генетического алгоритма сетями Петри 53
2.5 Решение задачи 57
2.6 Выводы по второй главе 57
Глава 3. Имитационная модель формирования конфигурации ДО с динамической структурой 59
3.1 Формальная постановка задачи 59
3.2 Формализация сетями Петри 59
3.3 Описание генотипа 64
3.4 Целевая функция 65
3.5 Операторы генетического алгоритма 66
3.6 Решение задачи 67
3.7 Модель межкомпонентной шины
3.8 Выводы по третьей главе 72
Глава 4. Разработка системы имитационного моделирования конфигурирования ДО 73
4.1 Функциональная модель информационной системы имитационного моделирования ДО с заданным поведением 73
4.2 Программная реализация 77
4.3 Применение предложенного метода в предметной области проектирования вычислительной техники 80
4.4 Пример работы адаптированного генетического алгоритма 83
4.5 Применение предложенного метода к проблемной области распределения ресурсов 94
4.6 Применение предложенного метода к решению задачи массового обслуживания 102
4.7 Оценка эффективности работы генетического алгоритма 109
4.8 Выводы по четвертой главе 119
Заключение
- Средства поиска конфигураций с заданным поведение
- Описание генотипа сетями Петри
- Целевая функция
- Применение предложенного метода в предметной области проектирования вычислительной техники
Введение к работе
Актуальность работы. Дискретное модельное описание является характерным не только для технических, но и для технологических, организационных, экономических, биологических и других типов объектов, что делает целесообразным изучение общих подходов и методов разработки и исследования моделей для такого рода «дискретных» объектов (ДО). Свойством дискретности может обладать структура, поведение и время функционирования объектов.
Один из основных этапов создания ДО - этап конфигурирования, то есть определение состава элементов и межэлементных связей.
Критериями эффективности решения задачи конфигурирования являются качество полученного решения и затраты связанные с получением этого решения. Принятие решения при формировании конфигураций ДО осуществляется на основе генерации возможных структурных и функциональных моделей объекта, оценки этих моделей и выборе среди них лучшей альтернативы - такого варианта возможной модели ДО, которая функционирует должным образом, т.е. способна преобразовывать заданный входной сигнал в требуемый выходной сигнал.
В настоящее время имеются методы, позволяющие формализовать процедуру параметрического синтеза объекта, однако, отсутствуют эффективные методики, обеспечивающие структурное конфигурирование объекта с заданным поведением. Во многом это связано со сложностью моделей, учитывающих динамическое изменение связей в процессе функционирования объекта.
В основу работы положены три актуальных научных направления: имитационное моделирование, эволюционные методы и сети Петри.
Имитационное моделирование - один из мощных инструментов решения задач синтеза, который целесообразно использовать при конфигурировании объектов. Он дает возможность специалисту экспериментировать с проектируемыми и существующими объектами в случаях, когда делать это с реальным объектом невозможно или нецелесообразно. Разработке теоретических основ имитационного моделирования и применению этой методологии посвящены работы Н.Н. Моисеева, А.А. Самарского, В.П. Строгалева, Ю.И. Рыжикова, Р. Шеннона и др.
Эволюционные методы представляют собой современный математический аппарат нахождения эвристических решений сложных задач, основанный на понятии эволюции, что обуславливает их применение при конфигурировании ДО. Теоретические и прикладные вопросы применения эволюционных методов рассматривались в работах А.Г. Ивахненко, Н.И. Корсунова, В.М. Курейчика, Д. Э. Попова, Дж. Холанда, В. Ф. Хорошевского и др.
Сети Петри, как математический аппарат моделирования динамических дискретных систем, являются удобным формальным и графическим языком для моделирования систем с параллелизмом. Этот язык представляет собой обобщение теории автоматов, в котором может быть выражена концепция одновременно происходящих событий, что позволяет применять данный математический аппарат при создании сложных дискретных объектов. Описанию и применению данного математического аппарата посвящены работы В.Е. Котова, С.А. Юдицкого, В.З. Магергута, И. А. Ломазовой, Дж. Питерсона, и др.
Актуальность темы диссертационного исследования связана с необходимостью совершенствования методов разработки и исследования математических моделей сложных распределенных процессов функционирования дискретных технических и организационных систем.
Целью диссертационной работы является разработка и исследование имитационных моделей дискретных объектов с заданным поведением.
Поставленная цель определила следующие основные задачи исследования:
Выполнить анализ существующих математических моделей конфигурирования ДО;
Разработать имитационную модель формирования конфигурации ДО со статической структурой;
Разработать имитационную модель формирования конфигурации ДО с динамической структурой;
Выполнить программную реализацию конфигурирования ДО на основе разработанных математических моделей.
Методы исследований. Для решения поставленных задач использовались методы системного анализа, эволюционных вычислений, теории сетей Петри (СП) и дискретной математики.
Научная новизна диссертационной работы состоит в следующем:
Разработана имитационная модель конфигурирования дискретных объектов, учитывающая возможность динамической перестройки структуры, на основе математического аппарата вложенных сетей Петри и генетических алгоритмов;
Предложено представление моделей дискретных объектов в виде сетей Петри для кодирования генотипа в рамках генетических алгоритмов при решении задач конфигурирования;
Предложен подход к формированию критериев качества конфигурирования объектов, используемый в рамках генетического алгоритма для построения функции приспо со б л енно сти.
Практическая значимость. На основе полученных моделей и алгоритмов разработана информационная система формирования конфигурации ДО с заданным поведением для решения задач обработки информации в произвольной предметной области. Практическая значимость подтверждается актами о внедрении отдельных результатов диссертационных исследований на ООО «Завод моющих средств» (г. Шебекино) и в Белгородском государственном технологическом университете им.В.Г.Шухова.
Положения, выносимые на защиту:
Способ построения конфигураций ДО с использованием генетических алгоритмов, описанных вложенными сетями Петри;
Метод поиска конфигурации дискретного объекта с фиксированными межкомпонентными связями;
Метод поиска конфигурации дискретного объекта с перестраиваемыми межкомпонентными связями;
Архитектура системы имитационного моделирования дискретных объектов на основе разработанных методов;
Комплекс проблемно-ориентированных программ имитационного моделирования дискретных объектов с заданным поведением.
Достоверность и обоснованность результатов исследований определяются использованием современных методов исследований, корректностью математических выводов и компьютерного моделирования, а так же результатами вычислительных экспериментов.
Личный вклад соискателя
Все разделы диссертационной работы выполнены лично автором. Все изложенные в диссертационной работе результаты исследований получены либо соискателем лично, либо при его непосредственном участии.
В работах, опубликованных в соавторстве, лично автором выполнена адаптация и формализация генетических алгоритмов на основе инструментария вложенных сетей Петри [4, 7, 8], разработана концепция построения структур ДО с фиксированными и перестраиваемыми межкомпонентными связями [5, 6, 9, 12], разработан вычислительный алгоритм и модуль поиска конфигурации [13, 14].
Апробация результатов диссертации. Основные научные и практические результаты докладывались и обсуждались на 7 Международном форуме «Радиоэлектроника и молодежь в XXI веке» (Харьков, 2003), 8 Международном форуме «Радиоэлектроника и молодежь в XXI веке» (Харьков, 2004), Международной научно-практической конференции «Информационные технологии в науку и образование» (Харьков 2005), Международной научно-технической конференции молодых учёных БГТУ им. В.Г. Шухова (г. Белгород, 2009), Международной научной конференции «Проблемы управления, передачи и обработки информации (АТМ-ТКИ-50)» (г. Саратов, 2009), XIV Международной научно-производственной конференции "Проблемы сельскохозяйственного производства на современном этапе и пути их решения" (г. Белгород, 2010), на ежегодных научно-технических семинарах кафедры «Информационные технологии» БГТУ им. В.Г.Шухова (2008-2010 г.г.).
Публикации. Основные положения работы изложены в 12 печатных работах, из которых 3 в изданиях, рекомендованных ВАК РФ по научной специальности диссертационной работы. Получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Диссертационная работа состоит из введения, четырех глав, заключения и списка литературных источников из 139 наименований. Содержание работы изложено на 153 листах машинописного текста.
Средства поиска конфигураций с заданным поведение
Для наглядного представления структуры сети используется специальное начертание схемы, однолинейная схема, представляющая три провода трёх фаз в виде одной линии. На схеме отображаются линии, секции и системы шин, коммутаторы, трансформаторы, устройства защиты.
Структура сети электроснабжения может динамически изменяться путём переключения коммутаторов. Это необходимо для отключения аварийных участков сети, для временного отключения участков при ремонте. Структура сети также может быть изменена для оптимизации электрического режима сети [20, 46].
При рассмотрении технических объектов можно сказать, что это ограниченная область реальной действительности, взаимодействующая с окружающей средой, выполняющая определенные функции и имеющая структуру.
Под функцией понимают свойство объекта, используемое для преобразования входных величин, при внешних и дополнительных воздействиях и условиях работы, в выходные величины. Функция является объективно измеряемое свойство, которое может быть охарактеризовано параметрами объекта. Количество реализуемых системой функций соответствует количеству используемых физических свойств. Если система выполняет несколько функций, то различают общую и частные функции. Общая функция охватывает множество всех входных и выходных величин, которое характеризует рассматриваемый объект как одно целое. Частные функции делятся на: главные и вспомогательные - по их значению в выполнении задачи; основные и элементарные - по типу изменения изменений функций в процессе их выполнения [23].
Структура - совокупность элементов и отношений между ними внутри объекта. Элемент объекта при проектировании рассматривается, как одно целое, хотя он может иметь различную степень сложности. Если при рассмотрении элемента, не принимается во внимание его форма и внутреннее строение, а рассматривается только выполняемая им функция, то такой элемент называется функциональным. Для механической системы элементами могут быть: деталь, звено, группа, узел, простой или типовой механизм. Деталь - элемент конструкции не имеющий в своем составе внутренних связей (состоящий из одного твердого тела). Звено -твердое тело или система жестко связанных твердых тел (может состоять из одной или нескольких деталей) входящая в состав механизма. Группа -кинематическая цепь, состоящая из подвижных звеньев, связанных между собой кинематическими парами (отношениями), и удовлетворяющая некоторым заданным условиям. Узел - несколько деталей связанных между собой функционально, конструктивно или каким-либо другим образом. С точки зрения системы узлы, группы, простые или типовые механизмы рассматриваются как подсистемы. Самым низким уровнем разбиения системы при конструировании является уровень деталей; при проектировании - уровень звеньев. Элементы из системы можно выделить только после определения взаимосвязей между ними, которые описываются отношениями. Для механических систем интерес представляют отношения определяющие структуру системы и ее функции, т.е. расположения и связи. Расположения - такие отношения между элементами, которые описывают их геометрические относительные положения. Связи - отношения между элементами, предназначенные для передачи материала, энергии или информации между элементами. Связи могут осуществляться с помощью различных физических средств: механических соединений, жидкостей, электромагнитных или других полей, упругих элементов. Механические соединения могут быть подвижными и неподвижными. Неподвижные соединения делятся на разъемные и неразъемные [27, 94].
В вычислительной технике (ВТ) структуру представляют как совокупность её функциональных элементов и связей между ними. Элементами могут быть самые различные устройства - от основных логических узлов до простейших схем к примеру триггеры, транзисторы, диоды и т.д.. Структура может иметь графическое представление в виде структурных схем, с помощью которых можно дать описание устройства ВТ на любом уровне детализации [29].
Логические элементы представляют собой электронные устройства, в которых обрабатываемая информация закодирована в виде двоичных чисел, отображаемых напряжением (сигналом) высокого и низкого уровня. Логические элементы реализуют логические функции и называются логическими или цифровыми устройствами [51].
В цифровых устройствах сигналы обычно изменяются только в дискретные моменты времени, интервал Т между которыми называется тактом. По характеру связи между входными и выходными переменными с учетом изменения этих связей по тактам работы различают комбинационные устройства и цифровые автоматы. В комбинационных устройствах совокупность выходных сигналов в каждый такт работы однозначно определяется входными сигналами, имеющимися в этот момент на его входах [59].
Описание генотипа сетями Петри
Согласно постановке задачи, из всех возможных моделей объекта О необходимо выбрать такую, которая обладала бы заданным свойством. В качестве свойства объекта можно рассматривать его реакцию на входные сигналы. Другими словами, свойство объекта определяется тем, какой выходной сигнал выдает объект на поступающий входной сигнал. Поэтому у объекта О следует выделить входы и выходы, которые, естественно, будут моделироваться позициями сети PN. Множества входных и выходных позиций обозначим через IN и OUT соответственно. Л R Очевидно, IN с U IN; и OUTclJOUT; . І=І І=І Свойством объекта О будем называть пару неотрицательных целочисленных векторов 7 -L у) и 7 -(zUT 7ОШ) „IN где zv — число меток, поступивших в v-ую входную позицию хт „OUT перед запуском сети FN, zw — число меток, появившихся в w-ои выходной позиции после остановки сети PN, V0 и Wo - число элементов множеств IN и OUT соответственно. Следовательно, множество Р свойств, которыми может обладать проектируемый объект, моделируется множеством Z = {Zk} к=] 5 где Zk = (zfN, ZQUT J - модель свойства Рк в виде пары неотрицательных целочисленных векторов. Таким образом, поставленная задача сводится к следующей. Среди всех гипотетически возможных моделей PN объекта О найти такую, которая обладает свойством Ъу.
Проанализируем эту задачу. Для того чтобы проверить, обладает ли модель PN свойством Zk, необходимо сформировать эту модель, на ее вход IN подать вектор ZIN, запустить сеть PN и после ее остановки сравнить количество меток на выходе OUT с вектором Z0UT. Пусть все эти действия компьютер выполняет за I секунду. Для 10 компонентов по 10 экземпляров на обнаружение необходимой модели объекта О прямым перебором может потребоваться М=1010 секунд (317 лет), при этом нет гарантии, что среди возможных моделей существует необходимая.
Очевидно, что прямым перебором такие задачи решать неэффективно. Более того, ставить задачу нахождения модели, обладающей некоторым свойством, некорректно, потому что такой модели может не существовать. Поэтому переформулируем поставленную задачу следующим образом: среди всех гипотетически возможных моделей PN объекта О найти такую, которая ближе всего к свойству Zk.
Такая формулировка задачи требует определить меру близости модели PN к свойству Zk. Для этого сначала необходимо на вход IN модели подать вектор Z\N и получить на выходе вектор ZOUT- Меру близости будем определять, привлекая понятие метрического пространства [115] и рассматривая полученный вектор ZOUT И эталонный вектор ZOUT как элементы евклидова пространства 5R — множества упорядоченных наборов из Wo действительных чисел х = (х,,...,хШо) с расстоянием Pi(x y) = Zlxw-yw (2.6) w=l где y = (y„...,yWo). Чем меньше A(ZOUT,ZOUT), тем ближе модель PN к свойству Zk. Если рх ( оит оит) О s то модель PN обладает свойством Zk. Естественно рассматривать расстояние рх как целевую функцию.
Операторы ГА манипулируют генотипами, представленными в виде кодовой строки символов. В теории СП аналогом операторов являются переходы. Поэтому естественно моделировать операторы ГА переходами СП. Учитывая, что переходы манипулируют метками СП, необходимо использовать такое расширение СП, в котором метки могут моделировать кодовую строку символов. Таким расширением являются нагруженные СП. В нашем случае кодовая строка является СП. Поэтому можно воспользоваться расширением нагруженных СП, в которых метка является СП (макрометкой). К таким СП относятся L-сети Петри (L-СП) [35, 37, 38] и вложенные СП [61-63] .
Таким образом, операторы ГА будут моделироваться переходами L-СП, а генотипы - макрометками L-СП.
Множество генотипов, непосредственно обрабатываемое ГА, называется популяцией. Начальная популяция может формироваться либо автоматически (например, случайным выбором экземпляров компонентов), либо задаваться непосредственно разработчиками ДО. Обозначим начальную популяцию через G=(PN ,...,PN2n), где PN1 - і-ая модель конфигурируемого объекта в виде СП, 2п -фиксированный размер популяции. Здесь для простоты дальнейшего описания предполагается, что размер популяции является четным числом. Каждую модель PN1 разместим в соответствующей позиции А,- в качестве макрометки L-СП.
Оператор отбора моделируется переходом SEL, который будет копировать PN1 из позиции Aj и размещать эти копии в позициях Вь В2, ...,В2н, В2ь ..., В2п-ь В2п в качестве макрометок L-СП. Обозначим макрометки, размещенные в позициях B2;_i и B2j, через PNj2" и PNj21. Макрометки размещаются в позициях Вь ..., В2п в соответствии со значением целевой функции (6) по правилу: чем меньше значение функции (6), тем меньше номер позиции, в которой размещается макрометка. Таким образом, в позиции В і размещается самая лучшая макрометка, в позиции В2 — чуть худшая макрометка и т.д. до позиции В2п, в которой будет находиться самая плохая макрометка.
Целевая функция
Среди всех гипотетически возможных моделей объекта О необходимо найти именно такую, которая решает поставленную задачу: из имеющегося множества подсистем {Sk }=1 и системы переходов Т = tq} =1 построить такой объект О, который на входной вектор реагировала бы требуемым выходным вектором. Поэтому чем ближе выходной вектор к требуемому, тем сконфигурированный объект лучше.
Для оценки этой близости введем обозначение для требуемого вектора: V = (v15...,vn,...vN), где vn - количество меток, которые должны находиться в позиции put объекта О. Естественно, что vnє{0,1,2,3,...}. Вектор, который получился в результате работы объекта О, обозначим через W=(wi,...wn).. wN), где wn - количество меток, которые реально находятся в позиции put объекта О. Аналогично, wn {0,l,2,3,...}.. Разницу (расстояние) между требуемым и реальным вектором N можно оценивать, например, по формуле /?(V,W) = 2jvn _wn. n=l Выбор целевой функции влияет на эффективность работы генетического алгоритма. Поэтому на практике можно использовать и формулу, задающую классическое евклидово расстояние р(у, W) = IY (vn -Wn)2 , И реДКО ИСПОЛЬЗуемуЮ формулу /9(V,W)=maxvn-Wn. V n=l При программной реализации генетического алгоритма имеет смысл заложить в систему возможность работы с формулой f N V/P yo(v,w)= vn-wnp , которая при p=l, p=2 и p—юо представляет собой U=l J рассмотренные выше формулы. Изменяя параметр р, можно будет влиять на эффективность работы генетического алгоритма.
Чем меньше р, тем ближе объект О к требуемой конфигурации. При р = О объект полностью соответствует заданному требованию. Но, тем не менее, нет гарантии того, что из заданного множества подсистем \Sk}k=1, их моделей PNk = {tkrf=]k и связей T = {tq}Q=i можно построить требуемый объект О.
После выбора целевой функции можно описать операторы генетического алгоритма. Оператор отбора должен отбирать для скрещивания те генотипы, которые ближе всего к требуемой конфигурации. Организовать этот процесс можно описать, например, следующим образом: упорядочить все имеющиеся генотипы по качеству (от лучшего к худшему) и скрещивать соседние пары. Можно также разрешить лучшим генотипам участвовать в нескольких скрещиваниях.
Оператор скрещивания можно описать следующим образом. Рассмотрим два генотипа G, =(g{,...,gj,gj+1,...g{j,hj,...,hjt,h[+1,...,hc) и G2=(gf,...,g gJ+1,...gJ,hI2,...,h h +1,...,h ). Случайным образом выбираем два числа: q из диапазона (множества) {1,2,...,Q} и к из диапазона {1,2,...,К}. А затем меняем соответствующие участки генотипов. Таким образом из родителей G] и G2 получаются потомки G3 и G4, наследующие свойства родителей: G3=(g;5...,g;,g2q+1,...gj,h;,...,hk,hk+1,...,h2K) G4=(gf,...,gJ,g!I+i,...gQ,hf,...,h2,h[+1,...,h1K). Можно ограничиться и выбором какого-то одного числа (q или к). Сколько чисел будет выбрано (одно или два) и если одно, то какое именно, можно также определять случайным образом. Можно также выбрать для каждого диапазона ({1,2,...,Q} и {1,2,...,К}) по две точки и меняться «серединками».
Оператор мутации можно описать следующим образом. Рассмотрим один генотип G=(gi,...,gq,...gQ,hb...,hk,...,hK). Случайно выбираем два числа: q из диапазона {1,2,...,Q} и к из диапазона! 1,2,...,К}. А затем меняем значения gq и h следующим образом. Если было gq=0, меняем его на единицу: gq=l. И наоборот: если было gq=l, то станет gq=0. Если было hk=r, то меняем его на любое другое из диапазона {0,1,...,г-l,r+l,...,R(k)}. Естественно при г=0 это будет диапазон {l,...,R(k)}, а при r=R(k) это будет диапазон {0,l,...,R(k)-l}.
Оператор редукции должен удалять слабые генотипы. Для этого после скрещивания необходимо определить качества всех потомков. Затем потомков и родителей объединять в одно множество генотипов и упорядочить их по качеству от лучшего к худшему. Кто оказался в худшей половине, тот удаляется.
Перед началом работы операторов генетического алгоритма необходимо задать начальную популяцию генотипов. Если есть какие-либо гипотезы о структуре и функционировании объекта О, то генотипы может описать сам модельер. Иначе можно случайно сгенерировать несколько генотипов. Размер популяции также определяется модельером.
Процесс работы генетического алгоритма можно также описать сетью Петри (рис. 7) так, как это делалось в работе [118].
Начальная популяция генотипов G],G2,...G2D размещается в позиции сети Петри. Оператор SEL осуществляет отбор генотипов для скрещивания. Операторы CROSSi,...,CROSSd,...,CROSSD осуществляют скрещивание генотипов, которые затем подвергаются мутации оператором MUT. Цикл работы завершает оператор RED, удаляющий слабые генотипы. Затем процесс повторяется.
Остановка этого циклического процесса может определяться разными способами: - заданием определенного числа циклов; - заданием нижнего предела качества р всей популяции; - заданием нижнего предела качества р части популяции (например, половины).
В частном случае перестройки структуры объекта О может происходить с использование межкомпонентной шины (МШ). Данный метод наиболее часто используется при конфигурировании ДО и требует отдельного рассмотрения.
Вся система элементов ДО и шин обрабатывается последовательно от входа системы к ее выходу [44]. Сначала первый слой элементов получает и обрабатывает входные сигналы. Затем по первой шине сигналы передаются на второй слой. После обработки сигналы по второй шине поступают на третий слой и т.д. Процесс заканчивается после обработки сигналов последним слоем элементов, и выходной вектор сравнивается с искомым.
Формально, для каждой шины задано множество входных позиций In = {Inm} и множество выходных позиций Out = {Outm} (m = 1, 2, ..., М). Входные позиции — это выходы предыдущего блока элементов ДО, а выходные позиции - входы последующего блока элементов (рис. 3.8).
Применение предложенного метода в предметной области проектирования вычислительной техники
На основе разработанного метода поиск конфигурации ДО для обработки ресурсов имеет следующий вид:
Оператор SEL - формирует случайным образом генотипы, на основе предложенной неправильной сети (рис. 4.22), заполняя подсистемы ДО элементами для обработки ресурсов и устанавливает связи экземпляров с позицией Рв. Операторы CROSS и MUT - работают по методам описанным в главах 2, 3 в соответствии с архитектурой ДО (фиксированная или перестраиваемая). Оператор RED - может оценивать генотип: - по количеству и степени обработки ресурсов оставшихся в позиции Рв; - по количеству обработанных ресурсов в позициях Pout; - по двум приведенным выше критериям одновременно. Примером использования предложенной модели может служить поиск конфигурации ДО: для обработки заявок, составление расписания учебного процесса, системы энергопотребления и т.д.
В случае применения предложенной математической модели к задаче формирования расписания в качестве подсистем объекта могут выступать типы аудиторий (лекционные, аудитории для практических занятий, аудитории для лабораторных занятий и т.д.). Количество переходов закачки в моделях С, соответствует количеству студенчески групп способных обрабатываться аудиторией.
Маркер принадлежности к совместному использованию D — индикатор потока для проведения лекционных занятий (лекционное занятие может проводиться более чем с одной группой).
Маркер принадлежности к типу ресурсов G — индикатор специальности (ввиду того, что предметы на разных специальностях не всегда совпадают по своему наполнению материалом).
Маркер обработки ресурса М - состоит из количества и типа аудиторных занятий на учебный день.
Группы, выбранные для обработки на первом занятии, помещаются в позиции Pjn, после чего срабатывают переходы t;n, которые перемещают метки-группы в позицию Рв. Для уменьшения времени поиска решения расставляются приоритеты срабатывания подсистем. К примеру, первыми могут срабатывать переходы «закачки» экземпляров подсистемы лекционных аудиторий, которые случайным образом захватывают из позиции Рв метку-группу у которой в Месть лекционное занятие, после чего переходы экземпляра затягивают из Рв метки с соответствующим D и G . После насыщения подсистемы лекционных аудиторий срабатывают переходы лабораторных аудиторий, а затем практических.
После обработки М\ метки К окрашивается в выбранный нами цвет (например в желтый) и возвращаются в Рв .
Следующим шагом проверяется возможность срабатывания переходов tout, если у метки окрашены, в выбранный нами желтый цвет, все МІ, то метка покидает ДО (перемещается в Pout) После проверки на срабатывание переходов tout в позиции Pjn помещаются группы, которые выбраны для проведения второго занятия и срабатывают переходы tjn. Таким образом, в Рв к обработанным меткам добавляются новые метки для обработки. Приоритетом обладают группы с большим количеством окрашенных М,. Это используется для устранения пустот («окон») в расписании групп.
Алгоритм имеет следующее количество циклов: IN = (INl,IN2,...,INR), где IN— множество входных векторов для обработки тогда Н = Rm + бтах , где Н— количество циклов алгоритма, Rm — мощность множества IN; Qmax — максимальная мощность множества MB К из INR. На основе предложенной математической модели разработано и зарегистрировано в ФГУ ФИПС программное обеспечение [47]. На рисунке 4.24 показано главное окно системы, позволяющей производить составление расписания занятий в вузе в трех режимах: - автоматическом; - ручном; - комбинированном. Файл Списки Справочная информация Добавление объектов Настройка коэффициентов 4-1" - !=! ;! H V FASOGAV.1. Рисунок 4.24 Главная экранная форма На рисунке 4.25 представлена форма элементов (аудиторий) которые используются при составлении генотипа. 2 Сортироваггь u e CJ-Ci JC . t И И Аудитории Номер_аддитории (Численность Тип_занятия Оснащенность Корпус 523! 35 Л Комп Гк 416j_ 25 = С Комп Гк 33! 70;Л Нет ІУк 1 7011 50ІЛ Нет ;МЄХ ___ 25IC ;Комп jMex 7291 35Л ;Нет !Ук и
Система массового обслуживания (СМО) - система, которая производит обслуживание поступающих в неё заявок. Обслуживание заявок в СМО производится обслуживающими подсистемами. Классическая СМО содержит от одного до бесконечного числа подсистем. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на: - системы с потерями, в которых заявки, не нашедшие в момент поступления ни одной свободной подсистемы, теряются; - системы с ожиданием, в которых имеется накопитель бесконечной ёмкости для буферизации поступивших заявок, при этом ожидающие требования образуют очередь; - системы с накопителем конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя; при этом заявки, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряется.
Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), RANDOM (случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру. Решим задачу нахождения конфигурации СМО «Операционный зал банка» для ограниченного количество персонала при заданной средней длине очереди. В банке должен быть «Экономический отдел», отвечающий за два различных типа операций: выдачу инвестиций и работу со счетом. В этот отдел может образовываться очередь. После обслуживания отделом каждый клиент направляется к отделу «Платежей», в состав которого могут входить как кассы, так и банкоматы, для приема или перевода денежных средств. Отдел «Платежей» может обрабатывать заявки по приему денежных средств и валютно-обменные операции. При этом заявка обработанная «Экономическим отделом» имеет более высокий приоритет над остальными заявками. Очередь перед отделом «Платежей» может состоять из одной заявки без приоритета и нескольких заявок с приоритетом. Моделирование генерации заявок осуществляется на основе различных вероятностных законов.
