Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования

• Автор: Залюбовский, Вячеслав Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Новосибирск
• Количество страниц: 105 с. : ил.

1 Асимптотически точные алгоритмы для задач упаковки
1.1 Задача упаковки в контейнеры
1.1.1 В-регулярные функции
1.1.2 Класс задач К
1.1.3 Условия асимптотической точности алгоритма Л
1.2 Задача упаковки в полосу
1.2.1 Класс задач
1.2.2 Условия асимптотической точности алгоритма Лч
1.2.3 Учет частичного порядка
1.2.4 Задача календарного планирования и упаковка в
полосу
2 Метод ветвей и границ для задачи
упаковки в контейнеры
2.1 Представление допустимых решений
2.1.1 Представление решений задач упаковки
перестановками
2.1.2 Регулярные перестановки
2.1.3 Доминируемые решения и максимальные упаковки

2.2 Сравнение нижних оценок
2.2.1 Тривиальная оценка Ь
2.2.2 Оценка 1,2
2.2.3 Класс оценок Ь^
2.2.4 Процедура лифтинга и класс оценок Ь
2.2.5 Результаты вычислительных экспериментов
3 Задача календарного планирования
со складируемыми ресурсами
3.1 Задача календарного планирования
3.2 Математическая модель
3.3 Некоторые сведения из теории сетевого
планирования и Т-поздние расписания
3.4 Задача Р5а и формулировка основного
результата
3.5 Обоснование алгоритма решения задачи РБ7
на основе Г-поздних расписаний
3.6 Алгоритм проверки допустимости Т-позднего
расписания в задаче Рв0
3.7 Завершение доказательства основной теоремы
3.8 Полиномиально разрешимый случай
задачи МР5£Т
Заключение
Список публикаций автора по теме диссертации
Список литературы

Диссертация посвящена двум классам задач комбинаторной оптимизации, которые представляют интерес как с точки зрения теории, так и с практической стороны. Несмотря на то, что эти проблемы имеют совершенно различные области приложений, в их математической природе есть немало общего, и многие задачи упаковки можно рассматривать как специальные случаи моделей календарного планирования [44, 48].
В общем случае задачи упаковки заключаются в распределении некоторого множества небольших объектов («предметов») по более крупным объектам («контейнерам») с соблюдением предписанных условий для достижения заданной цели. Так, в одномерной задаче упаковки в контейнеры каждому предмету приписан положительный вес, а целью является упаковка всех предметов в минимальное число идентичных контейнеров заданной грузоподъемности. В задаче упаковки в полосу имеется один контейнер заданной ширины и неограниченной высоты, а каждый предмет характеризуется положительными шириной и высотой. Необходимо упаковать все предметы таким образом, чтобы высота занятой части контейнера была минимальной. При этом стороны предметов должны быть параллельны сторонам контейнера, вращение и наложения предметов не допускаются. Классификация задач упаковки и раскроя приведена в [36]
Даже в простейшем (одномерном) случае задача упаковки в контейнеры является ]УР-трудной в сильном смысле [14], поэтому основные

Оценка существенно улучшается: г(Ь2) = § и значение | является достижимым — для доказательства достаточно рассмотреть класс задач с 6к предметами веса |
Маловероятно, что существует полиномиальная процедура нахождения нижней оценки с лучшей оценкой наихудшего поведения, т.к. это означало бы полиномиальную разрешимость задачи РАЗБИЕНИЕ ([14], стр. 47).
Значение 1/2 может быть найдено за 0(п log п) операций, причем определяющим фактором является сортировка предметов, т.к. остальная часть алгоритма может быть реализована за линейное время.
Идея эффективного поиска максимума на интервале е £ [0, |] заключается в отслеживании наилучшего значения целевой функции для £ £ [0,5] при изменении 6 ОТ О ДО 1. Проверять нужно лишь те значения, для которых 6 или 1 — 6 совпадает с размером предмета Х{. Для каждого из таких «событий» необходимо скорректировать предметы этого критического размера, поэтому каждый предмет может инициировать не более одной корректировки. Поскольку эти корректировки могут быть сделаны за время 0(1), оценка Ь2 может быть вычислена с линейной сложностью при условии предварительной сортировки предметов [59, 60].
2.2.3 Класс оценок iffl
Перейдем к обсуждению двойственно допустимых функций, которые являются основой описания нижних оценок 1г? Как и ранее, предполагаем, что предметы имеют размеры жг- £ [0,1] и емкость контейнера 0 = 1.
Функция и : [0,1] —»• [0,1] называется двойственно допустимой, если для любого конечного множества S неотрицательных вещественных