Введение 2
1. Теоретические аспекты исследования задачи 5
1.1. Постановка задачи 5
1.2. Приближенный и точный алгоритмы 6
2. Реализация программы 9
2.1. Реализация консольного интерфейса 9
2.2. Реализация программной части 14
3. Экспериментальное исследование 33
3.1. Описание экспериментов 33
3.2. Анализ экспериментов 35
Заключение 37
Список литературы 38
Приложение 1
Теория расписаний является одним из разделов исследования операций. Данное направление в науке берет свое начало с известной работы Генри Гантта 1903г. (Gantt H.L.), предложившего то, что сегодня называют диаграммами Гантта, которые встречаются во многих работах по теории расписаний. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации. С 50-х годов 20-го века началось активное теоретическое исследование задач теории расписаний, следует отметить работы Джонсона, Джексона и Смита, а также монографии.
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона, Ленстры и др., Лоулера и др., Танаева и др., Брукера и др. [1, С.9]
Подавляющее большинство исследованных задач теории расписаний являются NP-трудными. Несмотря на это, практика требует решения таких задач.
Задачам для одного прибор уделяется в рамках теории расписаний особое внимание в силу их тесной связи с классическими задачами из других областей дискретной математики, а также в связи с тем, что одноприборные задачи являются частными случаями и подзадачами более сложных практических задач.
Задачи теории расписаний широко применяются в таких областях, как планирование проектов, организация транспортных потоков, управление производством, ресурсами в вычислительных системах и т.д. Разнообразие методов решения задач теории расписаний, а также большие объемы обработки данных делают особо актуальной проблему построения быстрых и эффективных алгоритмов. Данная работа направлена на исследование точности приближенного алгоритма решения задачи минимизации взвешенного количества запаздывающих требований. Выводы, которые делаются в заключении данной работы дают оценку точности и эффективности работы приближенного алгоритма. Учитывая тот факт, что трудоемкость приближенного алгоритма гораздо меньше, чем точного, такая оценка в целом может быть полезной для оптимизации вычислений в областях, где приоритетом является скорость решения задач, а не точность. В этих случаях практическое применение такого алгоритма может принести значительные экономические выгоды предприятию.
Для указанной задачи достаточные условие оптимальности получены В.С. Танаевым и В.С. Гордоном [3]. В случае одновременного поступления алгоритмы решения разработаны Moore J.M., Kise H., Ibaraki T. и Mine H. в [8]. В случае одновременного поступления при условии возможности нумерации требований одновременно по неубыванию продолжительностей и не возрастанию весов предложен алгоритм В.С. Гордоном и В.С. Танаевым [1]. Решение задачи в случае единичных весов получено Kise H. [5], Maxwell W.I. [7], Lawler E.L. [6], Sidney J.B. [9].
Также полученные данные и выводы могут быть полезными при дальнейшем сравнении алгоритмов такой же трудоемкости, с целью выявления наиболее эффективного среди них алгоритма для данного типа производства и задач, решаемых на нем.
Основными целями данной работы являлись:
1) Разработка программного продукта, позволяющего исследовать задачу минимизации взвешенного количества запаздывающих требований с помощью приближенного и точного алгоритмов, а также обладающего удобным и функциональным диалоговым окном.
2) Исследование задачи минимизации взвешенного количества запаздывающих требований, заключающееся в сравнении результатов приближенного и точного алгоритма и оценке точности приближенного алгоритма
В процессе написания дипломного проекта была проделана работа в 3 этапа:
1. Изучение теоретических аспектов задачи минимизации взвешенного количества запаздывающих требований.
2. Реализация точного алгоритма и приближенного алгоритма с двумя модификациями в программном проекте.
3. Осуществление экспериментальных исследований и анализ полученных результатов.
Исходя из результатов исследования и анализа алгоритмов, можно сделать вывод, что при небольшом количестве требований лучше использовать второй метод. Значение его целевой функции часто совпадало с оптимальным значением, а если не совпадало, то не сильно от него отличалось (большинство неоптимальных решений попадают в первую группу). Однако при большом количестве требований второй метод сильно уступает первому методу, причем, когда требований становится больше 50 целевая функция второго метода всегда больше целевой функции первого.
