Введение 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) Сравнение и анализ результатов приближенных и точного алгоритмов.
В процессе написание дипломной работы выполнены такие этапы, как
1. Изучение теоретических аспектов задач теории расписаний, в частности методов решения задач минимизации максимального штрафа.
2. Программная реализация точного и приближенных алгоритмов.
3. Осуществление экспериментальных исследований и анализ полученных результатов.
Результаты, полученные только на небольших объемах данных, дают значения, достаточно точные для использования в дальнейших исследованиях. Однако было выявлено, что с увеличением количества требований значения штрафных функций приближенных методов все больше отличаются от значений, полученных точным методом. А при большом количестве требований первый и третий метод сильно уступает второму.
Исходя из результатов исследования, можно прийти к выводу, что при любых количествах поступающих требований, тестируемых задач и изменении целевой функции лучшим алгоритмом для минимизации максимального штрафа является второй алгоритм. Значение его целевой функции всегда было лучше остальных результатов приближенных алгоритмов и чаще совпадал с результатами точного алгоритма. Также можно сделать вывод, что худшим алгоритмом для решения данной задачи является первый, его результаты были хуже всех, тогда как результаты третьего алгоритма были недостаточно хороши в сравнении со вторым, но и незначительно, но лучше третьего алгоритма. Однако были такие тесты, в которых лучшим, в сравнении со вторым, оказывался третий или их показатели были одинаковы.
