Введение
ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 7
1.1. Возникновение и этапы развития теории расписаний 7
1.2 Способы представления расписаний 12
1.2. Классификация задач теории расписаний 13
1.3. Классификация алгоритмов решения 15
1.4. Классы P и NP 16
ГЛАВА 2. ЗАДАЧА МИНИМИЗАЦИИ СУММАРНОГО ШТРАФА 17
2.1. Постановка задачи 17
2.2. Свойства задачи минимизации суммарного штрафа 19
ГЛАВА 3. АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ 20
3.1. Алгоритмы 20
3.2. Построения оптимального расписания 22
ГЛАВА 4. ПРИБЛИЖЕННЫЙ АЛГОРИТМ С ВЫБОРОМ ДОПУСТИМОГО МЕСТА 24
4.1. Алгоритм 24
4.2. Построения расписания приближенным алгоритмом 29
ГЛАВА 5. АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННОГО АЛГОРИТМА 31
ЗАКЛЮЧЕНИЕ 37
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39
ПРИЛОЖЕНИЕ 41
На протяжении всего существования общество сталкивается с различными рода расписаниями. Чаще всего такие проблемы решатся автоматически. Однако и на примитивном уровне человек использует алгоритмы. Планирование строится на основании возрастания крайних сроков выполнения работ. Для решения ежедневных вопросов оказывается достаточно интуитивного подхода. Автоматизация производства, которая развивается довольно стремительно и нарастающий ставят все более трудоемкие задачи разработки алгоритмов составления расписаний.
Одним из разделов исследования операций является теория расписаний. Р. Беллман в 1956 году предложил термин «Теория расписаний». Для того, чтобы решить задачу комбинаторной оптимизации используются алгоритмы и методы решения задач теории расписаний.
Данная диссертационная работа проводит анализ ИР-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора.
NP- сложность задачи минимизации суммарного запаздывания для одного прибора, при условии одновременного поступления требований, была установлена Я.Ду и Ленгом[13]. Е. Лоулером [20] для решения этой задачи в теории, что продолжительности обслуживания pj,j = 1,п, -целые положительные числа, были построены псевдополиномиальный алгоритм трудоемкости О (п4Yj=iPj), который основан на методе динамического программирования, а также полиномиальный алгоритм с оценкой сложности 0(п7/Е). М.Я. Ковалеву [19]смог на порядок понизить эти оценки. В. Хорном были предложены более простые методы решения задачи. Для решения задачи минимизации суммарного запаздывания в [15,16] был применен Метод множителей Лагранжа был применен для решения задачи минимизации суммарного запаздывания.
Задача минимизации суммарного штрафа была сведена Е. Лоулером [21] к задаче о назначениях в случае единичных продолжительностей и одновременном поступлении требований, которую можно решить за 0(п3) операций [4]. Использованию метода динамического программирования для решения задачи минимизации суммарного штрафа также были посвящены работы[1,8,9,11,17], а использованию методов последовательного анализа вариантов - работы [6,10,12,14,22,23]. При дополнительном условии обслуживания требований задача минимизации суммарного штрафа без нарушения директивных сроков рассмотрена в [2,3,5].
Целью данной работы является разработка нового приближенного алгоритма для решения NP-трудной задачи теории расписаний- минимизации суммарного запаздывания для одного прибора, а также проведение сравнительного анализа его эффективности.
Научная новизна. Предложен новый метод нахождения приближенного решения NP-трудной задачи.
Теоретическая и практическая значимость. Приложенные методы могут быть полезны для решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть использованы специалистам, которые занимаются проблемами дискретной математики.
Магистерская диссертация состоит из введения, пяти глав, заключения, библиографического списка (24наименования). Содержит 12 таблиц и 13 иллюстраций. Комплексный объем диссертации составляет 78 страниц.
Результаты диссертации:
1. Реализован алгоритм построения допустимого расписания для NP- трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также приближенный алгоритм, для которого приведены экспериментальные оценки его эффективности.
2. На основе алгоритма построения допустимого расписания был реализован приближенный алгоритм с выбором допустимого места.
3. Проведен анализ результатов двух алгоритмов, в результате которого были выявлены некоторые соответствия.
4. Точный и приближенный алгоритмы реализованы в программном продукте "IntellijIDEA" и получил хорошее экспериментальное подтверждение.
Нахождение решения для задачи минимизации суммарного запаздывания является одной из приоритетных задач для комбинаторных задач теории расписаний. Она имеет связь с часто встречающейся задачей теории расписаний, смысл которой состоит в возможности проверить обслуживания заданного множества требований на одном приборе без прерываний и нарушений времени прихода и директивных сроков требований.
Главным результатом данной диссертационной работы является разработка приближенного алгоритма для решения NP-трудной задачи. В данном исследовании применялось четыре алгоритма с разными допустимыми местами, но количество алгоритмов может расширяться исходя из размерности и диапазона значений. В основе приближенного алгоритма лежит точный. Его суть состоит в том, чтобы ограничить выбор допустимого места, что позволяет уменьшить число ограничений, а также время работы алгоритма.
Одним из важных результатов работы является сравнительный анализ приближенного и точного алгоритмов. Можно сделать такие выводы:
1) Выбор первого места при малых размерностях показывает эффективность приближенного алгоритма, но, когда размерности увеличиваются, эффективность уменьшается.
2) Когда выбрано 2 допустимое место каких-либо изменений эффективности не наблюдается в 80% случаев.
3) Аналогично работает алгоритм при выборе среднего места в 75% случаев.
4) Когда выбирается последнее место при работе приближенного алгоритма алгоритм показывает эффективность в 60%.
Анализ эффективности показал, что наилучшие результаты приближенного алгоритма отображаются при выборе первого допустимого места.
Резюмируя, приближенный алгоритм может иметь применение и в других местах, однако, прошу заметить, что, как и у любого алгоритма, он имеет погрешности. Планируется применить данный алгоритм и для других задач комбинаторной оптимизации.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
