Введение к работе
Актуальность темы. Научные проблемы и методы теории расписаний имеют не только большое теоретическое значение, как связанные с решением задач, относящихся, в основном, классу NP-полных, но и характеризуются широким практическим распространением во множестве инженерных, экономических, управленческих и т.п. приложений. Во всех случаях, когда требуется упорядочить и распределить какие либо ресурсы между потребителями или исполнителями, возникает вопрос эффективного планирования такого распределения.
При решении задач подобных задач необходимо производить оценку вычислительной эффективности используемых алгоритмов. Эффективными алгоритмами принято называть такие из них, у которых время решения и требуемая память являются степенными функциями от размерности задачи. Важно отметить, что алгоритм может быть эффективным на одном классе задач и неэффективным на другом.
Как показывают теоретические исследования и накопленный вычислительный опыт, многие дискретные задачи эквивалентны с точки зрения их вычислительной сложности. Это так называемые универсальные или полиномиально полные задачи. Однако в настоящее время существует значительное число задач, имеющих экспоненциальную оценку сложности. К ним относятся задачи целочисленного и линейного программирования, вошедшие в научную литературу под различными образными названиями: задача о коммивояжере, задача о размещениях, задача о камнях, об обработке деталей на станках и т.д. Решением этих задач занимались известные отечественные ученые Алексеев О.Г., Романовский И.В., Поспелов Д.А., Тараканов В.Е., Горбатов В.Е. и многие другие. Не меньшее внимание методам решения таких задач уделяли их зарубежные коллеги: Кофман А., Дебазей Г., Карп Р., Гари Д., Грэхем Р. и многие другие.
Эффективность спланированного расписания в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Но при использовании точных методов решения, например, ветвей и границ (МВГ), построение оптимального плана распределения может занять многие месяцы и годы даже на современных многопроцессорных вычислительных системах. С другой стороны, применяемые сейчас для таких задач быстрые, но приближенные списочные методы, такие, как метод критического пути (МКП), могут давать большую погрешность, достигающую 30%. Такое отклонение от оптимума в большинстве случаев является неприемлемым. В связи с этим возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: обеспечивающих, с одной стороны, существенное снижение вычислительной сложности, а с другой, сохранение вычислительной точности (или незначительную её потерю).
Анализ проблемы показывает, что наиболее перспективными и эффективными в этом плане являются два подхода. Первый из них подсказывается всей историей развития математики – это переход от численных алгоритмов к аналитическим оценкам решения распределительных задач. Этот подход сулит как большие математические сложности, характерные для комбинаторных задач, так и значительный выигрыш во времени решения даже при получении сугубо частных результатов, т.к. аналитические оценки приводят к линейной зависимости вычислительной сложности от размерности задачи.
Второй подход опирается на разработку численных алгоритмов, характеризующихся полиноминальной зависимостью времени счёта от размерности задачи, но имеющих точность решения, близкую к предельной (или, по крайне мере, значительно лучшую, чем у МКП). Здесь, согласно данным проведённых исследований, успех сулит грамотное применение идеи т.н. «списочного» подхода к решению распределительных задач, суть которого состоит в придании исходным данным структуры, способствующей эффективной работе применяемого далее алгоритма решения. Кроме того, хорошо зарекомендовали себя эвристические, в частности, эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний день наиболее гибкими и эффективными из всех известных инструментов приближенного решения оптимизационных задач.
Таким образом, исследование возможности решения распределительных задач теории расписаний на основе сочетания аналитической оценки оптимальных распределений, полученных с помощью эффективных численных методов является весьма актуальной проблемой.
Цель работы. Основной целью диссертации является разработка и обоснование методологических основ и методов аналитической оценки результатов решения распределительных задач широкого класса, сущностью которой является количественное сопоставление экстремумов этих решений по различным критериям оптимизации, а также создание средств алгоритмической и программной поддержки сформулированной проблемы.
Объект исследований. Распределительные задачи теории расписаний сформулированные как в однородных, так и в ограниченного класса качественно и количественно неоднородных средах, в частности, при избирательных свойствах обслуживающих устройств относительно заданий
Предмет и направление исследований. Предметом исследований является комплекс методов и общая методология решения задач заявленной предметной области, а перспективными направлениями исследований является реализация научных идей по разработке новых методов решения задач, реализующих цель исследования. К ним относятся
разработка аналитических методов оптимизации вариантов решения распределительных задач для 2-4 приборных систем и, ограниченно, для n приборных систем;
разработка алгоритмов повышения эффективности точных методов решения распределительных задач в однородных и неоднородных средах;
разработка вероятностно-эвристических методов решения распределительных задач и оценки их оптимальных вариантов;
разработка эффективных методов приближенного решения оптимизационных распределительных задач, как инструмента повышения эффективности точного решения либо его оценки;
разработка и испытание системы обработки информации как средства программной и алгоритмической поддержки комплексного решения распределительных задач общего назначения.
Методы исследования. В диссертации применялись методы математического анализа, исследования операций, в частности, теории расписаний, методы теории вероятностей и математической статистики, а также методы алгоритмизации, программирования и имитационного моделирования. При реализации средств программной поддержки проведения исследований в области задач построения расписаний использовались методы объектно-ориентированного программирования и нормализации баз данных.
Содержательные научные результаты и степень их новизны
-
Идея и методология сопоставительно-критериальной оценки результатов решения и оптимизации распределительных задач, а также отдельные методы ее реализации для двух-четырехприборных и частных случаев n-приборных систем, аналогов которым в отечественных и зарубежных источниках не обнаружено.
-
Расширение понятия списочного подхода к параллельной обработке заданий распределительной системы на количественно и качественно неоднородные системы введением нормы векторной оценки ресурса выполнения каждого задания распределительной системы в целом и введением списочного приоритета качественно неоднородных оценок, что позволило повысить эффективность решения неоднородных распределительных задач за счет повышения (до 20%) быстродействия решения.
-
Алгоритмическая модификация точного алгоритма Алексеева, основанная на учете специфики качественной неоднородности решаемой задачи, позволяющая значительно уменьшить количество рассматриваемых вариантов и, соответственно, времени счета (приблизительно на 15%). При решении однородных задач модифицированный алгоритм, существенно выигрывает по быстродействию для двухприборных, а в некоторых случаях, и для трехприборных систем.
-
Алгоритмическая модификация метода Романовского, состоящая в формировании первого приближения на основе использования быстрых приближенных методов решения задачи, в частности, метода критического пути, генетического алгоритма, отличие которого от классического состоит в значительном для NP-полных задач (до 90%!) увеличении быстродействия.
-
Генетические модели распределительных задач, отличающиеся своеобразной структурой и статистически обоснованной совокупностью их настроек применительно к распределительным задачам теории расписаний, а также высокой вероятностью получения решения близкого к оптимальному, значительно превышающей соответствующие показатели других приближённых алгоритмов.
-
Обоснование метода использования генетического алгоритма как инструмента субоптимизации решения распределительной задачи, поддержанной статистически достоверной оценкой доверительности результата, согласно которому, например, можно найти оценку оптимума распределительной задач для работ и приборов с вероятностью более 0,999 на основе 7 опытов реализации ЭГА, требующих несколько десятков миллисекунд счёта (затраты на АА составляют сотни сек.).
-
Обоснование возможности применения первого приближения алгоритма Алексеева как самостоятельного метода решения распределительных задач, показавшее его более высокие критериальные характеристики по сравнению с распространенными приближенными методами, включая наиболее эффективный среди них - генетический.
-
Модифицированный алгоритм критического пути для решения распределительных задач в качественно неоднородных системах, отличающийся от имеющихся применением приоритетно-нормированного списочного подхода.
Достоверность результатов исследования. Достигается за счёт корректного применения системного анализа, методов математического анализа и моделирования, их статистической обработки. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более опытов. Минимальный статистически представительный эксперимент обеспечивался не менее, чем 100 опытами. Программное средство «Система для проведения исследований в области задач построения расписаний» («ProjectSheduler»), на котором осуществлялось автоматизированное проведение имитационных экспериментов в однородных средах, прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2007612127 (роспатент) от 23.05.2007). Другое программное средство «Система вычислительных исследований неоднородной распределительной задачи» находится в «Роспатенте» на рассмотрении.
Практическая значимость диссертационной работы определяется несколькими составляющими:
почти двукратное снижение ресурсоемкости решения задач оптимизации в многоприборных системах при использовании многокритериальных оценок;
существенное (до 20%) снижение времени решения неоднородных и однородных распределительных задач точными алгоритмами, являющихся основным инструментом оценки оптимального решения;
создание универсального приоритетно-ориентированного списочного подхода, позволяющего с единых позиций формировать решение как однородных, так и неоднородных задач, позволяющее снизить временной ресурс решения на 20%, а также дает инструмент псевдоточного решения распределительных задач, который может использоваться в качестве эталонного при размерностях недоступных для точных методов;
в теорию расписаний введен новый эффективный инструмент решения неоднородных распределительных задач, основанный на первом приближении метода Алексеева, превосходящий по эффективности все известные приближенные алгоритмы, что повышает возможности проектировщиков реальных систем;
апробирована совокупность программных комплексов решения распределительной задачи в различных средах и с различными критериями оптимальности, а также настраиваемыми параметрами и характеристиками распределительных задач [54], что позволяет решать практически всю гамму распределительных задач теории расписаний и создает основу для построения проектно-исследовательского и учебного программного комплекса поддержки решения задач изучаемой предметной области.
Кроме того, работа дала хорошее практическое приложение в учебном процессе, т.к. предложенные решения позволяют изучать на практике задачи комбинаторики, теории расписаний, а также применения ЭГА и других алгоритмов поисковой оптимизации. Автором опубликованы пособие и многочисленные методические указания по теме «Теория расписаний» (см. список публикаций) для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование».
Соответствие диссертации научному плану работ и целевым комплексным программам. Тема диссертационной работы сформулирована в соответствии с тематическим планом ДГТУ, а также лежит в русле проблем и задач перечня «Приоритетные направления развития науки, технологий и техники» (Пр-843 от 21 мая 2006 года) и перечня «Критические технологии …» (Пр-842 от 21 мая 2006 года) утвержденных Президентом Российской Федерации.
Апробация диссертационной работы. Материалы диссертационной работы апробировались на четырнадцати международных научных конференциях: «Использование ЭВМ в учебной и научно-исследовательской работе студентов» - тез. докл. на респ. совещ.-семинара, 26-28 янв. / НГУ.- Новосибирск, 1988.- Ч. II; «Новые информационные технологии. Разработка и аспекты применения» - тез. докл. IV Всерос. науч. конф. с междунар. участием молодых ученых и аспирантов, 15 нояб.,/ ТРТУ.- Таганрог, 2001; «Компьютерное и математическое моделирование в естественных и технических науках» - тр. III Всерос. науч. internet-конф., сент.- нояб. / ТГУ. -Тамбов,2001.-Вып.13; «Электроника и информатика-2002»: тез. докл. IV Междунар. науч.-техн. конф., Зеленоград, 19-21 нояб. / МИЭТ (ТУ). - М., 2002. -Ч.2; «Новые информационные технологии. Разработка и аспекты применения»: тез. докл. пятой Всерос. конф. с междунар. участием молодых ученых и аспирантов, 28 нояб. / ТРТУ. - Таганрог, 2002; «Современные проблемы информатизации в технике и технологиях»: сб. тр. по итогам VIII Междунар. открытой науч. конф. / ВГТУ.-Воронеж, 2003.-Вып.8; «Математические методы в технике и технологиях - ММТТ-16»: сб. тp. XVI Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2003. - Т. 8, секц.12; «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем»: материалы II Междунар. науч.-практ. конф., 21 мая / ЮРГТУ (НПИ). – Новочеркасск, 2004; «Математические методы в технике и технологиях – ММТТ-17»: сб. тр. XVII Междунар. науч. конф. / КГТУ. – Кострома, 2004. - Т.2, секц.2; «Математические методы в технике и технологиях» - ММТТ-18: сб. тp. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. – Т. 2, секц. 2; «Современные проблемы информации в непромышленной сфере и экономике»: сб. тр. - Воронеж, 2005. – Вып. 10; «Математические методы в технике и технологиях - ММТТ-19»: сб. тp.XIX Междунар. науч. конф./ ВГТА. - Воронеж, 2006. – Т. 2, секц. 2; «Математические методы в технике и технологиях - ММТТ-20»: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. – Т. 2, секц. 2; Труды 8 международной научно-технической конференции «Динамика технологических систем», - Ростов н/Д, Том 2; «Математические методы в технике и технологиях - ММТТ-21»: сб. тp. Междунар. науч. конф./ ВГТА. - Саратов, 2008. – Т. 5.
Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета, Таганрогского радиотехнического университета (ныне - ТТИ ЮФУ) и Новочеркасского политехнического института (ныне – ЮРГТУ).
Публикации по теме диссертационной работы. Всего по теме диссертационных исследований опубликовано 62 работы, из которых 11 - самостоятельные публикации, а 51 – работы опубликованные в соавторстве. В этих работах освещены наиболее существенные результаты диссертации, а в совместных работах автору принадлежат определяющие их результаты. При этом 9 работ опубликовано в изданиях из перечня ВАК.
Структура диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложений. Общий объем работы составляет 317 страниц машинописного текста, в том числе 78 рисунков и 45 таблиц.
