Введение 3
2 Цель работы 5
3 Теоретическая часть 6
3.1 Постановка задачи 6
3.2 Алгоритмы 8
3.2.1 Процедура hO 8
3.2.2 Метод ветвей и границ (В&В) 10
4 Исследования 13
5 Работа интерфейса 41
6 Заключение 45
Список литературы 49
Приложения 50
Объектом исследования данной работы является NP-полная задача теории расписаний. Такого рода задачи имеют большое практическое применение в организации производства, в индустрии сервиса, в бизнесе, в оптимизации компьютерных вычислений и в других различных сферах человеческой деятельности.
Задачи теории расписаний связаны с поиском расписания с наилучшим значением целевой функции. Существуют как приближенные, так и точные методы поиска оптимального расписания. Потому предметом исследования будет являться приближенный алгоритм вычисления для решения такого рода задач. Сравним приближенный метод с точным и проведем некоторые исследования по их работе.
Несмотря на то что вначале задачи теории расписаний применялись в моделировании производственных процессов, скоро стало ясно, что похожие задачи возникают и в других областях человеческой деятельности, например, в организации оптимальной работы современных вычислительных устройств. Очень быстрое развитие компьютерных технологий создает огромное количество задач в теории расписаний.
Большая часть задач теории расписаний являются NP-трудными. Надо понимать, что поиск точных алгоритмов решения для них, время работы которых ограничено полиномом от размера входа задачи, сегодня представляется бесперспективным. Для экспоненциальных алгоритмов, использующих перебор, необходимы значительные вычислительные затраты даже при решении примеров со средней размерностью. Поэтому одним из важных направлений исследований сегодня является построение и анализ приближенных алгоритмов для NP-трудных задач.[4]
Так как для многих задач не обязательно находить точные ответы, а достаточно построить хорошее и разумное решение за короткое время, то приближенные алгоритмы будут весьма удобны и полезны. Также
приближенные методы используются с целью поиска свойств оптимальных решений или подсказывают новые идеи для эвристик, которые затем применяются в практических задачах.
Следовательно, исследованием и изучением одного такого приближенного метода мы и будем заниматься в данной работе.
В итоге мы провели различные эксперименты, в которых пытались выяснить, как ведут себя приближенный и точный методы при одинаковых условиях в задаче минимизации максимального временного смещения.
В очередной раз убедились, что точный метод дает лучший результат, чем приближенный.
В экспериментах выясняли, когда оба метода будут давать схожий результат и когда в результатах будут заметные отличия значений целевой функции. Проанализировали в каждом эксперименте, когда и в какой момент будет видна разница в работе двух алгоритмов. А для моделирования условий использовали параметры требований.
Вводили такие величины, как: max offset — максимальное значение отклонения, offsets number — число отклонений из общего числа рассмотренных примеров. Эти понятия использовались, чтобы проанализировать, как работают метод ветвей и границ и процедура hO относительно друг друга.
Таким образом, мы сделали несколько выводов и предположений:
• Так мы узнали, что наблюдается тенденция, при которой увеличение числа требовании приводит к уменьшению как максимальной величины отклонения от точного решения - max offset, так и числа отклонений от точного решения - offsets number.
• Рассматривали случаи, когда параметры R, Р и D принимают константные значения. В случае одинаковых значений моментов поступления R или директивных сроков D заданных требований получим, что точный и приближенный методы будут давать одинаковые решения поставленной задачи. При Р = const выяснили, что
в первой половине интервала [from, to] достигается пик максимального числа и величины отклонений. И при увеличении числа требований этот пик смещается к началу интервала [from, to]. Сравнили результаты, когда Р = const и когда Р - случайно сгенерированное значение из интервала [from, to]. И выяснили, что при увеличении числа требований значения max offset и offsets number при Р = const будут становиться больше, по сравнению с произвольно заданным параметром Р для заданных требований
Поэкспериментировали с порядком задания значений параметра Р: по невозрастанию, по неубыванию. К тому же задавали способы, как именно будут убывать или возрастать значения Pf.
• При условии < PN выяснили, что если среди значений
| Pt — Pj-il i = 2, N есть такое, которое сильно отличается от остальных, то мы скорее всего увидим резкое увеличение величины и числа отклонений от точного решения, в отличие от того, если бы — Pf-J i = 2,N не сильно отличались друг от друга.
• При условии Рг > ••• > PN иная ситуация. Стоит отметить, что среди всех экспериментов данное условие дает наименьшее число отклонений от точного решения. Наличие резких увеличений (скачков) значений |Pf — Pj-i| , ведет к уменьшению числа отклонений от точного решения offsets number, но зато приводит к увеличению величины максимального отклонения max offset. И наоборот, если значения параметра Р для требований Рг, ...,PN будут давать не сильно отличающиеся значения |Pf — Pi_t| V i = 2,N , то результаты приближенного и точного методов будут более близкими друг к другу, а количество отклонений от точного решения offsets number становится больше.
Так же провели два отдельных эксперимента, связанные с выбором расстояния h, соответственно для параметров Dp R( с условиями:
1) Dt - Dj-il =h, Vi = 2JV
2) |Z?£ -Kf-il = h, Vi = 2Л
• Для параметра D начальное увеличение значения h приводит к резкому увеличению числа отклонений от точного решения. Затем, достигается пик — максимальное значение offsets number, а при дальнейшем увеличении величины h величина offsets number становится меньше и начинает стремиться к 0. Это означает, что достигнув точки максимума увеличение h приводит к тому, что решения приближенного метода ставятся все ближе к решениям точного метода. И начиная с определенного h, оба метода работают одинаково. Аналогичная ситуация складывается с величиной максимального отклонения от точного решения max offset, только пик максимального отклонения в данном случае достигается медленнее при увеличении значения h. Так же стоит обратить внимание, что увеличение числа требования при таких условиях приводит к увеличению числа отклонений от точного решения - offsets number.
• Для параметра R увеличение значения h приводит почти к тем же выводам, что и в случае при параметре D, рассмотренном выше. Отличие в том, что при увеличении числа требований смещается пик — максимальные значения offsets number и max offset. То есть, чем большее число требований, тем при большем h достигается пик. Также можно отметить, что с ростом числа требований уменьшаются и число отклонений и максимальная величина отклонения от точного решения.
Так же сделали интерфейсную реализацию работы двух методов. Для их сравнения применяются одни и те же условия, которые задаются с помощью входных параметров. Интерфейс предлагает удобный ввод входных данных, моделирующих условия, которые нас интересуют. А на выходе получаем результаты о работе двух алгоритмов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
