ВВЕДЕНИЕ 3
1. ОБЩИЕ СВЕДЕНИЯ О ТЕОРИИ РАСПИСАНИЙ 6
1.1. Предмет теории расписаний 6
1.2. Возникновение и этапы развития теории расписания 9
1.3. Способы представления расписаний 13
1 .4. Классификация задач теории расписаний 14
1.5. Дополнительные условия в задачах теории расписаний 15
1.6. Целевые функции в задачах теории расписаний 16
2. ПОСТАНОВКА. ЗАДАЧИ ТЕОРИИ РАСПИСАНИЯ 17
2.1. Точный алгоритм 19
2.2. Приближенный алгоритм 21
3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ 25
3.1. Платформа для реализации 25
3.2. Описание работы 28
4. СРАВНИТЕЛЬНЫЙ АНАЛИЗ 35
ЗАКЛЮЧЕНИЕ 50
СПИСОК ЛИТЕРАТУРЫ 52
ПРИЛОЖЕНИЕ
Задачи упорядочения носят самый общий характер. Они возникают повсюду, где существует возможность выбора очередности выполнения работ. Изучаемые в теории расписаний модели возникают при календарном планировании производства, транспортных перевозок, военных операций, обучения, информационно-вычислительных процессов и при других видах целенаправленной деятельности. На практике большинство задач, так или иначе, решается. Однако эти решения принимаются интуитивно, так как принятие наилучшего решения связано с большими временными затратами. Поэтому вопросы построения эффективных по времени алгоритмов составления наилучших расписаний остаются актуальными.
Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком, тем самым они минимизируют максимальное временное смещение. Так как лучше получить на экзаменах три четвёрки, чем две пятерки и одну тройку,— стипендии не будет. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом всё более и более трудные задачи разработки алгоритмов составления расписаний.
Тема магистерской диссертации посвящена теории расписаний - одной из самых популярных с теоретической и практической точек зрения области исследования операций. Задачи теории расписания, разумеется, связаны с построением расписаний, то есть с упорядочиванием некоторых работ по времени или по исполнителям. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, или, что
является более сложным, - нахождение оптимального допустимого расписания по тому или иному критерию оптимальности.
Большинство задач теории расписаний являются NP - трудными, и реализация поиска их оптимального решения требует больших временных затрат. Поэтому исследование свойств оптимальных расписаний и построение на их основе эффективных приближенных алгоритмов, а также точных алгоритмов решения частных случаев задач являются актуальными проблемами теории расписаний.
В магистерской работе исследуются задачи теории расписаний для одного прибора — задача минимизации максимального временного смещения. Первым подходом решения таких задач является разработка полиномиальных эвристических алгоритмов. Для многих эвристических алгоритмов были найдены оценки погрешности получаемого решения. Такие алгоритмы называются приближёнными. Существуют приближённые алгоритмы, гарантирующие как относительную погрешность, так и абсолютную погрешность. Точным методам решения NP-трудных задач также уделено немалое внимание в работах по теории расписаний [16]. Наибольшее распространение получили методы сокращённого перебора, также называемые методами ветвей и границ.
Цель исследования заключается в экспериментальном исследовании приближенного алгоритма решения теории расписаний - минимизации максимального временного смещения. В соответствии с целью исследования в магистерской диссертации решаются следующие задачи: запрограммировать все необходимые алгоритмы и отладить программы, разработать удобный для проведения экспериментов и их анализа интерфейс, провести эксперименты и сравнить результаты.
В рамках диссертационного проекта была затронута тема теории расписаний- экспериментальное исследование приближенного алгоритма решения задачи минимизации максимального временного смещения. Исследованы задачи теории расписаний для одного прибора. Было построено множество допустимых расписаний, при котором соблюдены все ограничения.
В магистерской диссертации решены следующие задачи: запрограммированы все необходимые алгоритмы и отлажены программы; разработан удобный для проведения экспериментов и их анализа интерфейс; проведены эксперименты; проведено сравнение результатов.
В работе было запрограммированы пять алгоритмов: точный алгоритм - метод ветвей и границ применительно к указанной задаче, и приближенный алгоритм, который включает в себя четыре вспомогательных алгоритма.
С помощью графиков было рассмотрено, как меняется эффективность алгоритма 4 с изменением диапазона значений. Эффективность увеличивается, когда разница между значениями времени обслуживания и диапазоном значений момента поступления обслуживания и директивным сроком превышает 35.
При получении результатов работы приближенного метода решения задач и экспоненциального точного метода можно сделать следующие выводы:
1. Существенным оказывается влияние на алгоритм 4 размерность расписаний. В первом эксперименте, когда можно перенумеровать одновременно по невозрастанию моментов поступления требований и по
невозрастанию директивных сроков с ростом размерности, приближенный алгоритм работает хуже. А также эффективность алгоритма 4 ниже, чем в других частных случаях.
2. Приближенный алгоритм для частного случая строит больше оптимальных расписаний при условиях, когда можно перенумеровать по невозрастанию моментов поступления требований и по неубыванию директивных сроков. Но, тем не менее, эффективность снижается при росте размерности.
3. Проведенные эксперименты показали, что при одинаковых продолжительностях обслуживания требований, алгоритм 4 строил расписание ближе к оптимальному решению, чем в предыдущих частных случаях, однако, при росте размерности так же эффективность падала.
Программный проект может использоваться для исследований по задаче минимизации максимального временного смещения, а также для решения практических задач, позволяющих моделирование в терминах теории расписаний.
Данная работа может быть рекомендована к применению в любой отрасли, где существует планирование производственных, транспортных и учебных расписаний. Например, планирование расписаний автобусных перевозок или составления расписаний занятий в учебных заведениях.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
