Методы решения задачи минимизации суммарного запаздывания для одного прибора и задачи разбиения

• Автор: Кварацхелия, Александр Гонерович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Казань
• Количество страниц: 126 с. : ил.

1 Исследование комбинаторных свойств задачи 1 11

1.1 Постановка задачи суммарного запаздывания для одного прибора

1.2 Алгоритмы построения оптимальных расписаний, основанные на декомпозиционных свойствах задачи
1.3 Построение оптимальных расписаний в случае фиксированного количества запаздывающих требований

1.4 Оценки ЯРТ расписаний

1.4.1 Первая оценка

1.4.2 Вторая оценка

1.4.3 Задача построения набора требований с заданным оптимальным значением целевой функции

1.5 Результаты экспериментальных исследований

2 Полиномиально и псевдо- полиномиально разрешимые случаи задачи 1 ] |

2.1 Свойства оптимальных расписаний

2.2 Описание похода к решению примеров задачи

2.3 Алгоритм В
2.4 Алгоритм В-к
2.5 Алгоритм С
2.6 Алгоритм В-п
З Исследование свойств и приложения Алгоритма В-1
3.1 Свойство В
3.2 Алгоритм решения задач разбиения
3.2.1 Постановка и полиномиальная сводимость задач о разбиении
3.2.2 Алгоритм В-1-канонический
3.3 Алгоритм В-I-модифицированный
Заключение
Указатель обозначений
Список литературы
В теории расписаний основное внимание уделяется вопросам оптимального распределения и упорядочения конечного множества требований, обслуживаемых детерминированными системами с одним или несколькими приборами при различных предположениях относительно характера их обслуживания [27]. Изучаемые в теории расписаний задачи выбора очередности обслуживания имеют самый общий характер и возникают при различных видах целенаправленной деятельности, например, при календарном планировании производства, транспортных перевозок, обучения, информационно-вычислительных процессов.
Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы [49], в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний [48, 78, 72] выяснилось, что большинство рассматриваемых задач являются трудоемкими для решения. Поэтому, значительная часть работ в этой области посвящена исследованию и выявлению сложности задач1. Обзоры по задачам теории
1 На данный момент наиболее полная и постоянно обновляемая классификация КР-трудных и открытых задач теории расписаний приведена на сайтах

п - количество требований
Рис. 1.4: Средняя трудоемкость решения примеров с помощью Алгоритмов А и БВА
примеров алгоритмами, использующими декомпозиционные свойства задачи, возрастает практически линейно с ростом п. Поэтому, одним из актуальных направлений исследований является нахождение трудоемких для решения случаев, получение для них свойств оптимальных расписаний и построение соответствующих алгоритмов решения.
Исследование эффективности одного приближенного алгоритма
Рассмотрим одну модификацию Алгоритма А, с помощью которой за полиномиальное время можно строить приближенное решение примеров. Зафиксируем величину Я - значение, которое будет ограничением на требуемую трудоемкость нахождения приближенного решения.
Процесс работы нашего алгоритма разбит на два этапа. На первом этапе осуществляется построение дерева подпримеров Алгоритма А "во фронт",