Содержание к диссертации
Введение
ГЛАВА 1. Современное состояние моделирования планирования расписаний технологических систем 12
1.1 Проблемные вопросы, связанные с теорией расписаний 12
1.2 Синтез моделей планирования расписаний технологических систем 17
1.3 Модели многокритериальной оптимизации в задачах планирования расписаний технологических систем 23
1.3.1 Специфические особенности выбора решений в моделях оптимизации в задачах планирования 24
1.3.2 Методы выбора решений в моделях оптимизации в задачах планирования расписаний 29
1.4 Выводы, цель и задачи исследования 34
ГЛАВА 2. Модель календарного планирования расписания технологических систем 36
2.1 Структурная и системная модели планирования расписаний технологических систем 36
2.2 Структурная модель информационной технологии модели планирования расписаний технологических систем 46
2.3 Общая постановка задачи планирования расписаний технологических систем 51
2.4 Постановка задачи планирования расписания для сессии ВУЗа (частный случай общей постановки задачи планирования расписаний) 61
2.5 Выводы 69
ГЛАВА 3. Модели решения задачи планирования расписаний технологических систем 70
3.1 Построение оптимального набора функций и механизмов выбора 70
3.2 Модели и алгоритмы выбора на итерациях поиска 83
3.2.1 Алгоритм поиска сочетаний по приоритетным матрицам связи 83
3.2.2 Алгоритм выделения оптимального по Парето множества на итерациях поиска 86
3.2.3 Алгоритм экспертного выбора на базе экстраполяции экспертных оценок по функции максимального правдоподобия 89
3.3 Выводы 94
ГЛАВА 4. Программная реализация результатов исследования 95
4.1 Пакет прикладных программ реализации задачи планирования расписаний 95
4.2 Графические диаграммы UML для реализации пакета прикладных программ задачи планирования расписаний 105
4.3 Пример реализации программного обеспечения задачи планирования расписаний для сессии ВУЗа 109
4.4 Выводы 124
Заключение 125
Список литературы
- Модели многокритериальной оптимизации в задачах планирования расписаний технологических систем
- Структурная модель информационной технологии модели планирования расписаний технологических систем
- Модели и алгоритмы выбора на итерациях поиска
- Графические диаграммы UML для реализации пакета прикладных программ задачи планирования расписаний
Введение к работе
Актуальность темы. В настоящее время неотъемлемой частью любых процессов, протекающих в технологических системах (ТС), является задача построения наилучших в том или ином смысле календарных планов (расписаний) операций ТС - задача планирования (ЗП), которая включает задачи оптимального выбора и распределения ограниченных ресурсов во времени на различные технологические операции в соответствии с целями системы.
Необходимость решения этих проблем связана с тем, что любой ТС для достижения поставленных перед ней целей требуются различного рода ресурсы, которые ограничены в своих объемах.
Особенностью решения ЗП является необходимость нахождения оптимальных по некоторому набору критериев сочетаний технологических параметров, которые в реальном времени обеспечивают реализуемость функционального назначения ТС.
Многоцелевой характер ЗП и многоальтернативность получаемых решений делают необходимым разработку модели планирования (МП), позволяющей осуществить многоцелевой оптимизационный процесс моделирования расписаний в условиях векторной оценки эффективности функционирования ТС и применение аппарата теории выбора в численных схемах многокритериальной оптимизации (МКО) для поиска решения.
Отметим, что процесс поиска решения ЗП можно представить как совокупность актов принятия решений (ПР) на всех его фазах. С этих позиций центральным компонентом ЗП является задача ПР, что обуславливает необходимость процедурного описания актов ПР.
Существующие в настоящее время методы многокритериального поэтапного выбора в ЗП являются недостаточно эффективными и характеризуются узкой направленностью, связанной с конкретной предметной областью и жестко заложенными численными схемами и алгоритмами и, как правило, основаны на случайном выборе или различных способах дискретизации. При этом нет объективных оснований — почему был сделан выбор той или иной части множества вариантов.
Ввиду исключительного многообразия практических ситуаций, возникающих при решении ЗП расписаний ТС, первостепенное значение приобретает исследование системных связей между параметрами с целью построения МП и синтеза информационных технологий (ИТ), обеспечивающих гибкую настройку для различных предметных областей. Также возникают проблемные вопросы разработки алгоритмического и программного обеспечения процедур планирования расписаний сложных ТС в рамках инвариантных процедур МКО с учетом специфики выбора решений на этапах поиска.
Актуальность темы исследования определяется необходимостью повышения эффективности решения ЗП расписаний ТС на основе внедрения новых ИТ в различные сферы человеческой жизнедеятельности.
Диссертационная работа выполнена в рамі»* фаща__й__99-01-00327
Российского фонда фундаментальных исследова«іЙ,Р59<НЛ0|М»НАЛЬк \
I БИБЛИОТЕКА )
1, ygyf?
Цель и постановка задач исследования. Целью диссертационной работы является разработка и исследование математических моделей планирования расписаний ТС в структурно-параметрическом представлении, обеспечивающих построение инструментальных средств в виде математического, информационного, алгоритмического и программного обеспечения автоматизированных систем поддержки принятия решений.
Достижение цели исследования предполагает решение следующих задач:
провести системное моделирование, декомпозицию, построение структурной МП и синтез информационной технологии ЗП расписаний ТС;
разработать модели и алгоритмы решения ЗП расписаний ТС, обеспечивающие многоцелевой оптимизационный процесс моделирования в условиях векторной оценки выбора решений;
построить инструментальные средства в виде моделей данных предметной области, алгоритмов и пакетов прикладных профамм (ППП) поддержки принятия решений в ЗП расписаний ТС;
провести апробацию результатов работы и экспериментальных исследований на реальных примерах планирования расписаний ТС.
Методы исследования. Выполненные исследования базируются на использовании теории множеств, исследования операций, теории расписаний, теории графов, векторной оптимизации, выбора и принятия решений, математического моделирования и профаммирования, объектно-ориентированного проектирования. Общей методологической основой является системный подход.
Научная новизна;
системные модели планирования расписаний ТС, отражающие структуру элементов процесса и связи между ними, и создающие основу для его математического моделирования;
структурная модель ИТ, позволяющая произвести декомпозицию общей МП расписаний ТС в виде кортежа частных моделей, элементы которого последовательно формируют этапы ее выполнения в рамках одной из схем решения задач векторной оптимизации;
математическая модель и алгоритм планирования расписаний ТС, отличающиеся от существующих использованием аппарата теории выбора для получения множества альтернативных решений и выбора на нем окончательного на итерациях поиска в условиях векторной оценки эффективности процесса;
МП расписаний ТС, учитывающая, в отличии от известных, два вида связей, позволяющих устанавливать отношения между множествами входных параметров и учитывать особенности формирования требований и сочетаний параметров, необходимых для их обработки.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию обоснованы корректным использованием математического аппарата. Они подтверждены вычислительными экспериментами и актами внедрения результатов исследования для планирования расписаний.
Практическая значимость и результаты внедрения. В рамках диссертационного исследования разработаны инструментальные средства в виде предметно-ориентированных моделей, алгоритмов, модели данных и ППП, реализующих решение ЗП расписаний по заданным критериям оптимальности. Результаты диссертационной работы внедрены в учебный процесс ВГУ и В ГПУ. Эффект от внедрения - социальный.
Апробация работы. Основные материалы диссертации докладывались и обсуждались: на международных конференциях "Математика. Образование. Экология. Тендерные проблемы." (г. Воронеж, 2000г„ 2003г.); IX международной конференции "Математика. Образование. Экономика. Экология." (Чебоксары, 2001г.); второй региональной научно-методической конференции (г. Воронеж, 2002г.); 13-й международной конференции "Математика. Экономика. Образование." (г. Ростов-на-Дону, 2005г.); XI международной открытой научной конференции "ї-1овьіе технологии в образовании" (г. Воронеж, 2005г.); на научных сессиях ВГУ 2002г., 2005г.
Публикации. По материалам диссертации опубликовано 8 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 125 наименований и приложения. Работа изложена на 137 страницах машинописного текста (основной текст занимает 111 страниц), содержит 28 рисунков и 6 таблиц.
Модели многокритериальной оптимизации в задачах планирования расписаний технологических систем
При решении ЗП, как правило, преследуется множество разных целей. Такие многоцелевые задачи достаточно сложны в реализации [102]. Как правило, они описываются большим количеством качественных и количественных признаков, наличием сложных зависимостей между ними. Зачастую различные цели системы несоизмеримы. Для описания одной цели может использоваться несколько критериев оптимизации и между данной целью и ними наблюдается сложное взаимодействие. Моделирование и оптимизация параметров таких ЗП представляет собой задачу большой размерности. Одним из путей решения таких задач является привлечение эффективного аппарата многокритериальной оптимизации (МКО) [28, 29].
Численная реализация моделей МКО в задачах планирования -трудоемкая и кропотливая работа, требующая больших временных затрат, использования громоздких численных схем, связанная со значительным объемом вычислением. Существующее математическое обеспечение для ЗП характеризуется узкой направленностью, связанной с конкретной предметной областью и жестко заложенными численными схемами и алгоритмами и, как правило, основано на случайном выборе или различных способах дискретизации [31, 125]. При этом нет объективных оснований - почему был сделан выбор той или иной части множества вариантов.
Наряду с этим, в настоящее время активно развивается новое научное направление - теория выбора [3, 119, 122], позволяющая строить эффективные функции и механизмы выбора на множестве любой мощности, учитывать структуру и специфические его особенности, оценивать на ранних стадиях ПР эффективность работы того или иного способа выбора, принимать обоснованные и взвешенные решения, привлекая помимо мощного математического аппарата богатый опыт экспертов.
Функция выбора представляет собой наиболее естественное, универсальное и удобное описание для анализа концепции выбора при решении ЗП. Отсюда определяется необходимость выражения в терминах функций выбора результатов, формируемых на других языках теории ПР в моделях МКО для ЗП. Также возникают проблемные вопросы разработки алгоритмического и программного обеспечения этапа планирования для сложных ТС в рамках инвариантных процедур МКО с учетом специфики выбора проектных решений на этапах поиска.
Использование процедур МКО для решения ЗП накладывает ряд организационных и вычислительных ограничений. Так, например, перебор большого количества вариантов недоминируемых решений от итерации к итерации ведет к переполнению памяти вычислительной среды, при этом увеличивается время поиска, уменьшается точность полученных решений.
Сведение же исходной векторной формы представления критериев на скалярное, требует теоретического обоснования причин выбора того или иного "главного" критерия или способа построения критериальной свертки, что, в свою очередь, снижает эффективность получаемого решения ЗП и требует подтверждения полученной скалярной модели [2].
Эффективным способом решения ЗП является прямое обобщение известных схем скалярной оптимизации на векторный случай, но здесь возникает проблема неуправляемого роста мощности недоминируемых решений на итерациях поиска, что приводит к необходимости разработки обоснованных процедур отсева [42, 70, 71], которые, как правило, основываются на случайном выборе. Принятие окончательного решения в ЗП на сформированном множестве недоминируемых альтернатив также затруднено [25, 27].
Эти особенности численных схем МКО в свою очередь предъявляют повышенные требования к математическому и программному обеспечению. Наиболее приемлемый путь решения задачи - это использование процедур, ведущих к повышению качества полученного решения ЗП. При этом необходимо проводить обоснованный выбор решений как на итерациях поиска, так и при принятии окончательного решения.
Формализуем математическую модель задачи многокритериального выбора. В общем случае рассмотренная ранее ресурсная модель (1.1) сводится к модели [106]; Q = (Q1CX),Q2(X),...,Qn(X)) i Opt, D;D[xD2x...xDm;X = {\i X1 B1,i=r } (1.2) гДХ ОЛ-Сад = 1,2,3,..., где Opt - оператор, реализующий некоторый принцип оптимизации; X -вариант решения, определяемый множеством X = (Xj,...,Xm) - технико-экономических, или количественных параметров и задающий параметрические ограничения на область поиска; Q - вектор критериев оптимизации; А, В -параметрические ограничения на область поиска D, представляющую собой множество различных вариантов решения; г ц - функциональные ограничения на область D.
Структурная модель информационной технологии модели планирования расписаний технологических систем
Построим структурную модель информационной технологии (ИТ) планирования расписания ТС (центра). ИТ - информационные технологии взаимодействия между подмножествами входных параметров и временных интервалов на входе системы и календарных планов на выходе и рассмотрим общие законы ее функционирования.
Определим модель ИТ в виде кортежа моделей Мит = МА. , MDxo, MA.Xg, MDXo, MXY, M , MRY 9 (2.6) Xs элементы которого формируют этапы выполнения ИТ (MAs AXs информационная модель (ИМ) множеств входных параметров As!s = 1,S, М. ИМ связи множеств входных параметров с входом ТС, MD - ИМ временных интервалов, MDoX - ИМ связи множества временных интервалов с входом ТС, MXY - ИМ преобразования входных объектов в выходной объект, Мта - ИМ связи выхода с множеством построенных расписаний, Мк - ИМ множества расписаний). В соответствии с Мит представим ИТ в виде информационной модели планирования расписаний ТС (рис.2.4.) и рассмотрим представленные в (2.6) модели. І ад
Информационная модель МА Й множества входных параметров A s, s = 1, S представляет собой нуль - граф: GA» =GA,,(A,(Xs),0), где A,(X,)=IA,J(XJ,A„2(X„)...,A„N,IX,JJ множества вершин, характеризующие множества входных параметров. Каждый параметр А5ПДх8 }ns ei,...,Ns представляется в виде массива информации Xs _ .
При том ИМ входных параметров формализуются в виде A.n,(xsJ={As„,A(x)As„„„„»,(xsjAs„,(A4)j, где А\..„,(Х J множества исходной информации о входных параметрах As n„ Asns,ns,ns\Xs J множества дополнительной информации о входных параметрах As ns, A5ns (А\, ) -множества ограничений и требований, обуславливающих удовлетворение потребности в элементе множества As n, для других множеств входных параметров. При этом структура ns-ro входного параметра - это заданный граф A!n V n. A ,, ), а, - МНОЖеСТВО ИСХОДНЫХ И ДОПОЛНИТЄЛЬНЬЇХ Структур данных, а Ед1 - множество связей (дуг), соединяющие эти структуры.
Отметим, что множество дуг отображает множество Anj в само себя. Тогда граф GA, можно задать в виде GA, (АЛ, ,aSnsJ, включающего множество вершин A%s Х J и заданного на нем отображения a!„,.
Информационная модель MD]to множества временных интервалов представляет собой нуль - граф: GDX =GDK(D(XO)0), где D(X0)=(DI(X0IJID2(X0IJI...,D2(X0I)) множество вершин, характеризующее множество интервалов времени. Каждый интервал D XO ZEZ представляется в виде массива информации Х0г. При том ИМ интервала времени формализуется в виде оДх J= КК) D K), AZ(DZ)}, где Dzz(x0J - множество исходной информации об интервале времени Dz, Dm(x0 ) - множество дополнительной информации об интервале времени Dz, A,(Dz) - множество организационных требований, обуславливающих связь элементов множества D и элементов множеств Ая. При этом структура z-ro элемента множества D - это заданный граф GDz(Dz, EDJ, DZ - множество исходных и дополнительных структур данных, а EDZ - множество связей (дуг), соединяющие эти структуры. Отметим, что множество дуг отображает множество Dz в само себя. Тогда граф GDz можно задать в виде GD(Dz,pz), включающего множество вершин DZ(XZ) и заданного на нем отображения Pz.
Информационные модели MAs\s устанавливают отношения между множествами входных параметров модели МА.Й, s = l,S и множествами входных объектов Xs (рис. 2.4). Заметим, что нуль - графы GA, (As(Xs),0) порождают нуль - графы GXs„s \\ вПі / ), объединение вершин которых формирует входной объект Xs =jJX(ii . Тогда модели MA Xs представляются в виде двудольных графов, иА х
Модели и алгоритмы выбора на итерациях поиска
Опишем реализацию алгоритма поиска лучших по критериям группы (2.21 )-(2.22), отвечающим за приоритетные связи, сочетаний элементов множества требований с элементами из множеств параметров, необходимых для выполнения этих требований для ZV,00 =(x )n,Qfi),Ajii),E}ii),Mfil)) на итерациях поиска.
Пусть Qf =Q = (qi qP) - вектор критериев группы (2.21)-(2.22), отвечающих за приоритетные связи. Группа экспертов должна указать свои предпочтения в очередности выбора критериев. Пусть є = 1,Е? Где р; _ общее количество экспертов, оценивающих вектор критериев. В результате работы группы получаем совокупность векторов: є h — 1 Р Каждый р " - порядковый номер места, на которое эксперт є поставил критерий qp. Чем меньше значение этого номера, тем предпочтительнее при выборе решения в первую очередь учитывать критерий с таким номером с точки зрения эксперта є . Е Пусть с = (с„...,ср), ср = ХЬР Р = 1,Р. е=1 Введем дополнительное условие нормировки, то есть будем считать, что _ р вектор 0 = ( ,,.,,(: ) имеет единичную длину ( ср=1). Упорядочим элементы векторов критериев Q и коэффициентов, соответствующих этим критериям в порядке возрастания значений этих коэффициентов и получим векторы Q = (q, qP) и d-(di,...,dp), dL = c-j,(ij = 1,,.,,Р) соответственно.
Вектор критериев Q = (qi,...,qp) можно разбить на N P векторов критериев с одинаковыми соответствующими коэффициентами dp. Т.е. вектору Q = (Q\...,Qn,.",QN j соответствует вектор D = (D1,...,Dn,...,DN),rae Q-=(qr,...,q ).
Рассмотрим теперь алгоритм получения множества Х б из Х п, Его можно представить как итерационный процесс получения выборки решений по совокупности Q групп критериев, где число итераций будет равно числу групп критериев N. Каждая n-я итерация состоит из этапов, показанных на рис. 3.2.
Алгоритм получения Х б из Х ; представим как: 1. присвоение переменной цикла п=1; 2. синтез сочетаний параметров, связанных с требованиями по приоритетным связям с помощью вектора критериев Q"; 3. применение на полученном множестве решений механизма выбора MSka, или M Extra в зависимости от размерности вектора критериев, отвечающих за синтез новых параметров с множеством требований Q"; 4. продолжение итерационного процесса, если еще остались не рассмотренные группы критериев Q", т.е. присвоение переменной п=п+1 и переход на ш.2. при n N или выход из алгоритма в противном случае.
Вначале с имеющимся элементом е" (j = l,E") множества требований Еп синтезируем сочетания параметров, связанных с требованиями по приоритетным связям с помощью вектора критериев Q". ХП=е;х ,}х...х }, ГДЄ m1=1,...,N?1) mg = l,...,N , g n. X" -МНОЖЄСТВО допустимых на n-й итерации решений, среди которых необходимо выбрать лучшее. Если размерность вектора Qn равна 1 или размерность элементов множества X" увеличилась по сравнению с размерностью элемента е" на 1, то применяем на множестве Хп скалярный оптимизационный механизм выбора MSkal для критерия из Q", отвечающего за увеличение размерности элементов множества Хп. Для этого вычисляем значение этого критерия в точках Хл и берем элемент, отвечающий наименьшему.
В противном случае применяем М Ех1га на множестве X". Для этого к. вычисляем в его точках значение функции f(x") = J)d -q[n(x") и выбираем k .-1 элемент из X", соответствующий наименьшему. Далее обозначаем еУ+1 = е" х i \ jx „. х } и переходим на следующую итерацию, пока не получим окончательное решение.
Графические диаграммы UML для реализации пакета прикладных программ задачи планирования расписаний
Этап проектирования и моделирования при создании программного обеспечения занимает значительное время. Процесс правильного и грамотного проектирования непротиворечивой модели программного обеспечения является очень важным. Ошибку на этапе кодирования исправить горазда легче, чем просчет при начальном проектировании. Внутренне несогласованная или неполная модель может привести к полной неудаче проекта, невозможности кодирования и интеграции всех разрабатываемых приложений между собой или во внешнюю среду [66].
При проектировании программного комплекса информационной системы в образовании были использованы возможности унифицированного языка моделирования UML и программный пакет Rational Rose для визуального объектно-ориентированного моделирования систем на основе графических диаграмм языка UML.
UML (Unified Modelling Language) - это язык визуального моделирования программного обеспечения, включающий в себя определенную систему обозначений (нотацию), которая предназначена для обозначения идей и решений, выполненных на этапе объектно-ориентированного анализа и проектирования. UML включает в себя набор диаграмм, которые позволяют создавать модели сложных программных систем [50].
Rational Rose - это программный пакет для визуального объектно-ориентированного моделирования систем на основе классов и их взаимодействия. Другими словами, это визуальный редактор, позволяющий моделировать программные системы любой сложности на основе графических диаграмм языка UML. Rational Rose позволяет создавать модели будущей системы, удобные для понимания алгоритмов работы, взаимосвязей между объектами, по которым в дальнейшем создается программный каркас будущей программной системы. Сейчас моделирование - одно из средств, позволяющих значительно сократить время разработки, уложиться в бюджет и создать систему с нужным качеством. Модель будущей системы позволяет уже на стадии проектирования получить представление о поведении системы и избежать ошибок в дальнейшем, когда в написание кода вложены значительные силы. Диаграммы UML позволяют создать при помощи Rational Rose исходный текст программы на различных языках программирования и облегчить тем самым разработчику рутинную работу- написание кода программы. [113]
Определим требования к ППП, реализующему решение ЗП с помощью Use Case Diagram (диаграммы сценариев) (рис. 4.15). Этот вид диаграмм позволяет создать список операций, которые выполняет система. Также этот вид диаграмм называют диаграммой функций, потому что на основе набора таких диаграмм создается список требований к системе и определяется множество выполняемых системой функций. Каждая такая диаграмма - это описание сценария поведения системы, которому следуют действующие лица. Сформулируем требования к ППП; 1. оператор должен иметь возможность задавать параметры работы ППП; 2. оператор должен иметь запустить алгоритм решения задачи; 3. оператор должен иметь возможность смотреть протокол работы ППП и распечатать результаты работы ППП; 4. ППП должен уметь вносить изменения в БД и на основе полученных данных решать задачу и сохранять результаты на накопителе информации; 5. ППП должна иметь возможность внести изменения в печатную форму результатов работы программы; 6. ППП должен выдавать оператору протокол работы программы; смотреть результат ввести гире метры ЗП Внести изменения е печатную фэрму Построить решение Вывести печатную фэрму У X Накопитель информации (БД)
Построим диаграмму распределения классов и объектов по компонентам при физическом проектировании ЗП расписаний Component diagram (диаграммы компонентов). Также ее называют диаграммами модулей.
На нашей диаграмме (рис. 4.17) присутствуют значки. NewPackageSpec, MewPackageBody (см. рис. 4.16), которые позволяют отобразить определения пакета и описание пакета соответственно, которые обычно связаны между собой. В нашем случае совокупность этих двух значков - это файл с именем NewPackage и расширением pas, который условно можно разделить на две части -спецификация - то, что указано в разделе interface и исполняемая часть - то, что указано в разделе implementation. Для первого на диаграмме присутствует обозначение NewPackageSpec, для второго MewPackageBody.
На диаграмме (рис. 4.16) также присутствуют связи (Dependency). Для того чтобы какой-либо пакет (в нашем случае модуль) мог ссылаться на другой и использовать все его компоненты, необходимо в спецификации или в теле одного модуля указать ссылку на другой. Если ссылка указана в спецификации, то описания компонентов используемого модуля будут включены при компиляции, а в случае указания ссылки на используемый модуль в теле пакета, описания компонентов будут включены при запуске программного комплекса. Эта возможность позволяет модулям рекурсивно ссылаться друг на друга. Т.е. нельзя одновременно указать в спецификации ссылку из Unitl на Unit2 и из Unit2 на Unitl также, как и нельзя в теле пакета одновременно указать ссылку из Unitl на Unit2 и из Unit2 на Unitl.
На нашей диаграмме как раз и отражены связи модулей между собой. Опишем их подробнее. В нашу программу включены пять модулей: Unitl main, Unit 1 Edit ArchForm, Unit2_Stells, Unit3_Schedule, Unit3_Report_Excel. Сделаем пояснение об их названиях. Модули можно условно разделить на три группы. Начальная приставка в названии каждого как раз и означает, к какой группе относится модуль. Группа Unitl отвечает за графический интерфейс, визуально связывающий программный комплекс с пользователем. Unit2 - пакет с компонентами для связи программного комплекса с базой данных. Unit3 отвечает за математическую составляющую комплекса и за формирование отчетов пользователю.
