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

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

1 Оценка абсолютной погрешности задач минимизации

максимального временного смещения

1.1 Постановка задачи 1 | г,- | Lmax

1.2 Обозначения и определения основных понятий

1.3 Абсолютная погрешность приближённого решения

1.4 Схема нахождения приближённого решения

1.4.1 Вариант схемы на основе случая

1 | d{ 5^ dj j d{ Г| pi > dj тj Pj | Lmax

1.4.2 Вариант схемы на основе случая Хогевена

1.5 Экспериментальное исследование полиномиальных алгоритмов решения

задачи 1 | rj Lma.x

1.5.1 Способ генерации примеров
1.5.2 Оценка экспериментального значения
абсолютной погрешности
1.5.3 Эффективность применения полиномиальных
алгоритмов для общего случая задачи
1.6 Свойства оптимальных расписаний общего случая задачи l|rj|Lmai
1.7 Свойства оптимальных расписаний
частных случаев задачи lrjLmax
1.8 Оценки абсолютной погрешности
1.8.1 Задачи для нескольких приборов

1.8.2 Оценка абсолютной погрешности
1.8.3 Схема приближённого решения задачи Р | ргес,Г] 1Ьтлх
1.9 Нормированное пространство примеров
1.10 Схемы нахождения приближённого решения
1.10.1 Схема сведения задач а | р | Ьтах -> а | Р | Стах и
О' [ Р) Tj | Атах ^ СУ | Г? — 0 | 7/тах
1.10.2 Схема сведения задач а Р,р^ | Атах -> а | р,р^ = р Ьтах и
^ І РіРі I Т'тах ^ 01 | РіР] — 1 | •і'тах
1.10.3 Схема сведения задач {Я, <2} | /3 Ьтах -> Р | р | Атах
1.10.4 Схема сведения задачи Я | Р | Ьтах -> (3 (3 | ігаах
1.10.5 Схема сведения задачи
СУ 1 Д | -Т-тах ^ а|/1,р^ £ {Рь • • • )Рл}|Стах
2 Полиномиально и псевдополиномиально разрешимые случаи задачи
1 | ТІ | Дпах
2.1 Задача 1 | (і* < с/д ^ - г* - р* > Рі - г,- - pJ• | Дтах
2.1.1 Свойства задачи
2.1.2 Задача на быстродействие при ограничении на
максимальное временное смещение
2.1.3 Алгоритм построения множества Парето-расписаний
ПО критериям Стах И Ьтах
2.2 "Двойственная" задача
2.3 "Обратная" задача
3 Алгоритмы оптимального решения задачи 1 | г,- | £тах
3.1 Существующие методы решения задачи 1 | г,- | £тах
3.1.1 Алгоритм Карлье
3.1.2 Метод программирования в ограничениях
3.2 Алгоритмы решения задачи 1 | г,- | Ьгаах
3.3 Экспериментальное сравнение алгоритмов
решения задачи 1 | г,- | Атах

3.4 Модифицированный алгоритм Карлье
3.5 Эффективные алгоритмы решения задачи минимизации максимального временного смещения
3.5.1 Процедура построения приближённого решения задачи
1|ч < Г},Ь > ^Ьтах. Оценка абсолютной погрешности
3.5.2 Процедура построения допустимого расписания
для задачи 1|г4 < > ф|Ьтах
3.5.3 Алгоритм решения задачи 1|г,- < г;-,ф > <1^Ьтах
3.5.4 Полиномиальные алгоритмы решения частных случаев
задачи 1|г,- < г,-,ф > ^Ьтах
3.6 Приближённый алгоритм решения общего
случая задачи. Оценка абсолютной погрешности
4 Алгоритм ветвей и отсечений для решения задачи 1 | г;- |
4.1 “Гибридная” схема решения одного класса задач
целочисленного линейного программирования
4.2 Постановка задачи
4.3 Формулировка задачи 1 | г,- | как задачи ЧЦЛП
4.3.1 Дополнительные ограничения
4.4 Генерация отсечений
4.5 “Гибридный” алгоритм ветвей и отсечений
4.6 Экспериментальная оценка эффективности
5 Исследование свойств задачи 1 11
5.1 Постановка задачи суммарного запаздывания для одного прибора
5.2 Алгоритмы построения оптимальных расписаний, основанные
на "декомпозиционных" свойствах задачи
5.3 Построение оптимальных расписаний в случае фиксированного количества запаздывающих требований
5.4 Канонические примеры задачи 11| £7)
5.4.1 Задача ЧЁТНО-НЕЧЁТНОЕ РАЗБИЕНИЕ (ЧНР)

Следствию 1.2, перестановки / и / - оптимальные для примеров Е и Р, соответственно. Тогда по лемме 1
6С + А ,(Е,Р) > ЬЕ„(я?г)- ЬЕт^яЕ) > 0.

Р([{Е, Р) = тах{^ - } + тах{^ - df}.
1 1 3 * уелг 7
Согласно лемме 1.3, Р^Ю = Р^Дя^) и Р^аДя^) = Ртах^). Сле-довательно,
(УС + рДР, Р) > Ршах(^) - Ртах(^) > 0- (1-5)
Имеем: рДР, Р) = тах^-6дг{^ - дв} + тах^дДс/^ - дв} = тах;елг{г^ -г/} + тах,€дг{гТ — г^} = рг{В, С). Отсюда и из (1.5) следует утверждение леммы. □
Теорема 1.1 Пусть пример С наследует у примера А длительности обслуживания требований Тогда
0 < ^шах(^) - Ртах(7ГЛ) < Р(А Доказательство. Неравенство 0 < Р;')|ЯХ МО — Ртах(7!’Л) ВЫТекаеТ ИЗ ОП-тималыюсти расписания ттл для примера А. Докажем неравенство
Рассмотрим пример В = {(гв,рв,дв) € ТУ} с параметрами требований {г? = г^,рв — р^ = , дв = д*?} и его оптимальное расписание пв.
По лемме 1.4 имеем
££»№ - < Рг(В, с) = рГ(А, С). (1.6)
Из оптимальности яв для примера В
ЬЦО < (1-7)