ВВЕДЕНИЕ 3
1. ЦЕЛЬ ИССЛЕДОВАНИЯ 5
2. ОБЩИЕ СВЕДЕНИЯ О ТЕОРИИ РАСПИСАНИЙ 6
2.1 Возникновение и этапы развития теории расписания 6
2.2 Предмет теории расписаний 8
2.3 Способы представления расписаний 9
2.4 Классификация задач теории расписаний 10
2.5 Дополнительные параметры в задачах теории расписаний 12
3. АЛГОРИТМЫ. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 13
3.1 Постановка задачи 15
3.2 Метод ветвей и границ 15
3.3 Приближенный алгоритм 1 15
3.4 Приближенный алгоритм 2 18
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ПРОЕКТА 19
4.1 Платформа для реализации 19
4.2 Архитектура приложения 19
4.3 Описание разработанного приложения 19
5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ 32
ЗАКЛЮЧЕНИЕ 55
СПИСОК ЛИТЕРАТУРЫ 55
ПРИЛОЖЕНИЕ
На протяжении всей жизни люди сталкиваются с проблемой планирования своего времени. Например, мы знаем, какие дела нам нужно сделать сегодня и оцениваем, сколько на эти действия уйдет времени. Исходя из этих данных, мы строим план действий, то есть составляем некое расписание. Чаще всего составление расписания не составляет трудности для человека и, в основном все мы придерживаемся “похожими действиями”, то есть интуитивно мы понимаем, что и когда нам нужно сделать, чтобы сделать все дела вовремя. Возьмем конкретный пример того, как студенты готовятся к сдаче экзаменов. Например, одному студенту нужно сдать 3 экзамена с 3 днями на подготовку к каждому. Для получения положительного результата, в данном случае для получения стипендии, он не будет готовиться к первому экзамену, уча материал по третьему и наоборот. Таким образом, большинство студентов составят такое расписание: “первые три дня готовлюсь к первому экзамену, следующие 3 дня ко второму и последние три дня к третьему”.
Вся сложность появляется тогда, когда необходимо составить расписание, где нужно учесть множество дополнительных факторов и нюансов или, например, составить расписания не для одного человека, а для группы людей, в которой нужно учесть интересы каждого. Представьте себе сотни работ и десятки исполнителей, для которых необходимо составить расписание. Именно в таких случаях и появляется необходимость в изучении основ такой науки как теория расписания.
Отдельная наука теория расписания начала формироваться еще в середине 20 века с исследований Д.Х.Джексона[1] и Д.П.Джонсона[2]. Примерно в это время начинают формироваться новые области математики - теория многокритериального принятия решений, теория массового обслуживания, теория автоматического управления, теория оптимального управления и т.п.
Модели, изучаемые в теории расписаний, возникают во многих сферах человеческой деятельности: образовании, транспорте, при календарном планировании производства, управлении, информатике, сельском хозяйстве и т.д.
Таким образом, задачи теории расписания упорядочивают некоторые работы по времени или по исполнителям. Цель решения таких задач - построение допустимого расписания, при котором соблюдены все ограничения или найдено решение, удовлетворяющее тому или иному критерию оптимальности.
Практически все задачи теории расписания являются NP- полными, то есть это такие задачи, которые нельзя решить никаким известным полиномиальным алгоритмом и для решения подобных задач затрачивается много ресурсов и временных затрат. Поэтому исследование свойств оптимальных расписаний и построение на их основе эффективных приближенных алгоритмов, а также точных алгоритмов решения частных случаев задач являются актуальными проблемами теории расписаний. Чем мы и займемся в данной работе.
Для NP-полной задачи теории расписаний - минимизации максимального временного смещения проведено экспериментальное сравнение результатов работы приближенных алгоритмов.
Для проведения указанного исследования были выполнены следующие работы:
• Изучены метод ветвей и границ и приближенные алгоритмы.
• Все алгоритмы были запрограммированы.
• Разработан удобный интерфейс для использования приложения.
• Проведено множество экспериментов над работой алгоритмов.
• Проведен анализ полученных результатов.
По анализу результатов можно сделать вывод, что приближенный алгоритм 1 выдает оптимальный результат при поступлении примера с невозрастанием моментов поступления и неубыванием директивных сроков и наоборот. Приближенный алгоритм 2 показывает обратное. Кроме случая с неубыванием моментов поступления и невозрастанием директивных сроков алгоритм выдает близкие к оптимальным результаты. При случайных поступлениях требований оба алгоритма показывают средние показатели построения оптимального расписания. В среднем для 80-85% примеров приближенные алгоритмы выдают оптимальное решение.
