Введение 3
1. Теоретические аспекты исследования задачи 5
1.1. Постановка задачи 5
1.2. Приближенные и точный алгоритмы минимизации максимального
штрафа 6
2. Реализация программы 9
2.1. Реализация консольного интерфейса 9
2.2. Реализация программной части 15
3. Экспериментальное исследование 30
3.1. Описание экспериментов 30
3.2. Анализ экспериментов 31
Заключение 41
Список литературы 42
Приложение 1
Купить

В повседневной жизни мы встречаемся с различными расписаниями: телепередач, общественного транспорта, школьных/университетских занятий и т.п. Каждый из нас строит удобное для себя расписание своего дня. Для решения повседневных задач нам достаточно подсознательного подхода. К примеру, учащиеся во время экзаменов учат предмет с самым маленьким директивным сроком (ближайший по дате сдачи экзамен), так они минимизируют максимальное временное смещение. Ведь лучше одинаково быть готовым к пяти экзаменам и получить пять четверок, чем неодинаково и получить три пятерки и две тройки - можно лишиться стипендии. Но перед людьми поставлены и более серьезные проблемы. В наше время стремительно развивается автоматизация производства и появляется необходимость разрабатывать алгоритмы составления расписаний, в которых будут учтены разные ограничения.
Теория расписаний - это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений.
Цель теории расписания - составить оптимальное расписание, минимизирующее время выполнения работ, стоимость работ и т.п.
Теория расписаний используется в таких областях, как бизнеспланирование, логистика, управление ресурсами, производством и т.д. Разные алгоритмы решения задач теории расписаний и немалые объемы обработки данных делают особенно важным вопрос создания эффективных и быстрых методов решения задач. Данная работа направлена на исследование и сравнение приближенных алгоритмов минимизации максимального штрафа, а также их сравнение с более точным алгоритмом. Заключение, которое делается в выводах данной работы дают оценку эффективности и точности решения приближенных алгоритмов. А также полученные выводы могут быть
полезными для определения самого эффективного алгоритма для данной задачи. При том, что трудоемкость приближенного алгоритма значительно меньше, чем точного, эта оценка в целом может быть полезной для оптимизации вычислений в областях, где главным является то, насколько быстро можно решить задачу, а не ее точность. В таких ситуациях практическое применение такого алгоритма может принести внушительное экономическое преимущество предприятию.
Основными целями данной работы являлись:
1) Ознакомление с предметной областью, просмотр литературы. Изучение постановок и методов задач теории расписаний. Изучение методов решения задач минимизации максимального штрафа.
2) Программная реализация трех приближенных алгоритмов минимизации максимального штрафа в теории расписаний и разработка интерфейса проекта.
3) Сравнение и анализ результатов приближенных и точного алгоритмов.

Купить