Алгоритмы решения задач теории расписаний для одного прибора с критериями Lmax и ΣwjUj

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

1 Полиномиальные алгоритмы решения задачи 1 | г,- | Ьтах
1.1 Постановка задачи
1.2 Обозначения и определения основных понятий
1.3 Абсолютная погрешность приближенного решения
1.4 Схема нахождения приближенного решения
1.4.1 Вариант схемы на основе случая Лазарева
1.4.2 Вариант схемы на основе случая Хогевена
1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи 1 | | Атах
1.5.1 Способ генерации примеров
1.5.2 Оценка практического значения абсолютной погрешности
1.5.3 Эффективность применения полиномиальных
алгоритмов для общего случая задачи
2 Алгоритмы оптимального решения задачи 1 | г,- | Ьтдх
2.1 Существующие методы решения задачи 1 | г,- | Ьтах
2.1.1 Алгоритм Карлье
2.1.2 Метод программирования в ограничениях
2.2 Алгоритмы решения задачи 1 ( Гу [ Ьтяк
2.3 Экспериментальное сравнение алгоритмов
решения задачи 1 | г.,■ | Ьтах

2,4 Модифицированный алгоритм Карлье
3 Алгоритм ветвей и отсечений для решения задачи 1 | г.; |
3.1 “Гибридная” схема решения одного класса задач целочисленного линейного программирования
3.2 Постановка задачи
3.3 Формулировка задачи 1 | г;- | ад,И, как задачи ЧЦЛП
3.4 Дополнительные ограничения
3.5 Генерация отсечений
3.6 “Гибридный” алгоритм ветвей и отсечений
3.7 Экспериментальная оценка эффективности
Заключение
Список литературы

Общее направление исследований
В наше время люди все чаще и чаще сталкиваются с проблемами составления расписаний. В обычной жизни эти проблемы решаются интуитивно. Но даже на обыденном уровне человек исполняет алгоритмы, пусть даже не осознавая этого. Например, мы обычно планируем наши действия в порядке возрастания крайних сроков их исполнения. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно.
Однако, когда дело касается большого производства, целесообразным является использование настолько хороших расписаний, насколько это возможно. Улучшение расписания даже на несколько процентов может дать существенную экономию. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом все более и более трудные задачи составления расписаний.
Данное направление в науке, получившее название “теория расписаний”, берет свое начало в 50-е годы 20-го века. Одними из первых работ по теории расписаний считаются труды Джонсона (Johnson [53]), Джексона (Jackson [50]) и Смита (Smith [79]).
Изначально одними из главных вопросов нового направления были классификация задач и установление их сложности. Считающаяся стандартной и по нынешний день классификация задач теории расписаний была предло-

• иначе, если с 6 51 — наибольший такой индекс, что йс > <4, то в любом расписании к1, для которого ЬИШХ(тсг) < 13В, требование с выполняется или до, или после всех требований из множества
Доказательство. Заметим, что между требованиями из множества 3 в расписании я за прибор не простаивает. Если бы прибор простаивал, это означало бы, что существует требование а' Е в, а' > а, обслуживаемое сразу после простоя и удовлетворяющее ограничению (2.1), так как •V (яДс/О = г а/ = (согласно правилу построения расписания Шраге). И это бы противоречило условию, что требование а последнее такое требование.
Если не существует такого требования с € 5, что бс > бь, то с4 = тах;-65 бу Используя (2.1) и (2.2), имеем:
Согласно Лемме 2.1, левая часть неравенства (2.3) является нижней оценкой оптимального решения для данного примера, то есть не существует такого расписания я' Е П(ЛД что Лтах(тг) <11 В.
Пусть теперь существует требование г Е 3, (1; > (4- И пусть с - последнее такое требование, поэтому бь = таАналогично предыдущему случаю, так как между требованиями из А в язл отсутствуют простои, мы имеем ХДщ^) = 5с(^5с/г) + Рс + “ $»■ Заметим, что ведясь) <
тпще./щ, иначе существовало бы требование из 3, обслуживаемое перед требованием с в расписании Шраге я за (так как бс > бь — тахщ,; <4). Пусть требование с выполняется между требованиями из 3 в я1. Тогда временное смещение требования к Е 3 С IV, обслуживаемого последним среди
Поэтому,
(2.2)
нашrj + Vз ~ тах<4 > 13В.

(2.3)