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

Залюбовский, Вячеслав Валерьевич

Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Залюбовский, Вячеслав Валерьевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

На правах рукописи

ЗАЛЮВОВСКИЙ Вячеслав Валерьевич

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

(01.01.09 - дискретная математика и математическая кибернетика)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 2006

Работа выполнена в Институте математики им. С. Л.Соболева СО РАН

Научный руководитель: д.ф.-м.н., профессор Э. X. Гимади Официальные оппоненты: д.ф.-м.н., А. И. Ерзин

к.ф-м.н., доцент В. П. Ильев Ведущая организация: Институт вычислительной

математики и математической геофизики СО РАН

Защита состоится " 15 " марта 2006 г. в 15 часов на заседании диссертационного совета Д.003.015.01 в Институте математики им. С. Л. Соболева СО РАН (пр. Академика Коптюга, 4, 630090 Новосибирск).

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан февраля 2006 г.

Ученый секретарь

диссертационного совета

доктор физ.-мат. наук $Ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В силу того, что рассматриваемые задачи являются КР-трудными в сильном смысле, особый интерес представляет построение приближенных алгоритмов с априорными оценками точности.

Цель работы. Построение и исследование оценок качества как точных, так и приближенных алгоритмов для задач упаковки. Разработка рационального метода представления допустимых решений и анализ эффективности нижних оценок для задачи упаковки в контейнеры. Выделение полиномиально разрешимых случаев задачи календарного планирования с ограниченными ресурсами.

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

Научная новизна. На основе общего подхода — построения алгоритмов с оценками (е,6) для задач упаковки в контейнеры и полосу разработаны полиномиальные приближенные алгоритмы и представлены условия их асимптотической точности. Аналогичные результаты получены для задачи упаковки в полосу при задании частичного порядка на множестве прямоугольников. Исследована связь задачи упаковки в полосу с частным случаем задачи календарного планирования, для которого также предложен алгоритм нахождения приближенного решения и установлены условия его асимптотической точности.

Для одномерной задачи упаковки в контейнеры предложен новый способ представления решений и исследована эффективность нескольких методов вычисления нижних оценок значе-

<1>ОС. НАЦИОНАЛЬНАЯ ] ИБЛИОТЕКЛ

¿"да?:

ний целевой функции.

Доказана полиномиальная разрешимость задачи календарного планирования со складируемыми ограниченными ресурсами и директивными сроками. Для мультимодальной задачи выделен частный случай, когда предложенный полиномиальный алгоритм находит оптимальное решение.

Практическая ценность. Результаты работы имеют преимущественно теоретический характер. Алгоритм, предложенный в главе 3, может быть использован в системах управления проектами для решения задач календарного планирования.

Апробация работы. Основные результаты диссертации докладывались на 16-ой Европейской конференции по исследованию операций EURO XVI (Брюссель, 1998), на XII Международной конференции по проблемам теоретической кибернетики (Нижний Новгород, 1999), на Симпозиуме по исследованию операций SOR'99 (Магдебург, 1999), на 8-ой Международной конференции "IEEE Conference on Emerging Technologies and Factory Automation" (Франция, 2001), на 2-ом Международном совещании "Discrete optimization methods in production and logistics" (Омск, 2004), на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), на 13-ой Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Северобайкальск, 2005), на научных семинарах Института математики СО РАН.

Публикации. По теме диссертации автором опубликовано 14 работ.

Структура и объем работы. Диссертация изложена на 105 страницах, содержит введение, три главы, заключение и список литературы, содержащий 70 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во введении приводится обзор результатов, посвященных рассматриваемым задачам, обосновывается актуальность темы исследования и кратко излагается содержание диссертационной работы.

В первой главе рассматриваются задачи упаковки в контейнеры и в полосу со случайными входными данными. Для исследования качества приближенного алгоритма используется идея построения алгоритмов с оценками (е, 5), предложенная Э. X. Гимади, Н. И. Глебовым и В. А. Перепелицей 1

Пусть К, — некоторый класс оптимизационных задач. Посредством обозначим оптимальное значение целевой функции для задачи 5 6 /С. Будем считать, что рассматривается задача на минимум и F*(5) > 0 для всех Б £ 1С.

Пусть заданы класс задач /С и некоторое семейство V вероятностных мер, определенных на /С. Будем говорить, что алгоритм Л имеет оценки (е, 5) относительно V, если

для всех Р €Т.

Будем далее говорить о классах Кп задач размерности п, семействах Тп, оценках (еп,8п) и их свойствах в зависимости от параметра п.

Алгоритм Л называется асимптотически точным на классе задач /С, если существуют такие последовательности (еп, 8п), что для любого п алгоритм Л удовлетворяет оценкам (еп> 5п) на подмножестве Кп С К и при этом еп —► 0, 8п -* 0 при п —► оо.

1 Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975. Вып. 31. С. 35-42.

Параметры еп и 6п могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма соответственно.

В разделе 1.1 рассматривается следующая задача упаковки в контейнеры. Заданы список 5 = {а* | г = 1,..., п} предметов с весами 0 < Wi < В. Требуется разместить все предметы в минимальное число контейнеров таким образом, чтобы сумма весов предметов в каждом контейнере не превосходила В.

Пусть 1Ь = {1,2,..., Ь}, 6 > 0 — целое

Неотрицательную функцию / целочисленного аргумента г е 1в, будем называть Ь-асимметричной, если /(г) < /(£> — г) при г = 1,..., [Ь/2\, и /(г) = 0 при г > Ъ.

Неотрицательную функцию / целочисленного аргумента г 6 1в, назовем (Ь-симметричной), если /(г) = /(6 — г) при г = 1,..., [Ь/2\, и /(г) = 0 при г>Ь.

Функцию / будем называть В-регулярной при В = 2^, ф > О — целое, если она представима в виде суммы 2*-симметричных функций к € :

т = Е г € /в.

к=1

Важным подклассом В-регулярных функций являются невоз-растающие функции при 5 = 2*3, (5 > 0 — целое.

Исследуются задачи упаковки в контейнеры, задаваемые списками 5 = {а* | г € /„}, в которых веса предметов — независимые случайные величины с дискретным распределением вероятностей

рГ = Рг{^ = г} > 0, г = 1.....В; ]Грг = 1- (1)

г=1

Класс /С* содержит задачи упаковки в контейнеры со следующим механизмом формирования случайных списков: в ходе п

последовательных независимых испытаний очередной предмет а, попадает в один из весовых классов г = 1,..., В в соответствии с распределением (1).

Для решения задач из класса /С* предлагается алгоритм А\, имеющий линейную сложность, и для него доказываются следующие утверждения.

Теорема 1 Вероятность несрабатывания алгоритма Ах на классе задач К\ ограничена сверху величиной 0(В/п2).

Теорема 2 Алгоритм Ах на классе К}п задач упаковки в контейнеры с В-асимметричной функцией рг имеет оценку относительной погрешности

и асимптотически точен при В = о(п/\тхп).

Теорема 3 Алгоритм Ах на классе К.\ задач упаковки в контейнеры с В-регулярным распределением весов является асимптотически точным при

В/ар = о(п/\пп) ,

где ар = ± грГ.

Раздел 1.2 посвящен решению задачи упаковки в полосу. Имеется полубесконечная полоса ширины IV и список прямоугольных предметов 5 = {аг \ г = 1,..., п}. Предмет аг 6 5 имеет ширину гюг, 0 < и>г < У/ и высоту Нг > 0. Требуется упаковать все предметы из списка 5 в полосу минимальной высоты. Упакованные предметы не должны перекрывать друг

друга, их стороны должны быть параллельны сторонам полосы, вращение предметов не допускается.

Класс К?п состоит из задач упаковки прямоугольников в полосу (ЗУП) со следующей моделью формирования случайного списка 5 : производится серия п независимых испытаний, в каждом из которых очередной предмет а*, г = 1,... ,п, принимает свои размеры — ширину юг и высоту /ц — в соответствии с одинаковым дискретным распределением вероятностей

= Рг{гиг = и), Ы = к}> 0, ги = 1,..., 1У, И - 1,..., Я,

Матрицу назовем -регулярной (\¥ -асимметричной, Ш-симметричной, неубывающей), если таковым является каждый столбец матрицы.

Для решения задач из класса предложен полиномиальный алгоритм Л2, Для которого доказаны следующие утверждения.

Теорема 4 Если матрица {рши) является IV-асимметричной, то при V/Н = о(п/\пп) алгоритм Л2 приводит к асимптотически точному решению ЗУП из класса К?п\ при этом справедливы следующие оценки вероятности несрабатывания и относительной погрешности:

IV н

№=1 /1=1

Теорема 5 Если матрица (рюь) является IV-регулярной, то при

\¥Н/(3Р = о{п/\пп) ,

где /Зр = -¡^л ы^РтН, алгоритм Л2 приводит к асимп-

тотически точному решению задачи упаковки предметов в полосу из класса /С^; при этом справедливы оценки вероятности несрабатывания и относительной погрешности:

л - -п( 1шК

дл>~°\п\пп)' п/\пп

В разделе 1.2.3 рассматриваются задачи упаковки в полосу с отношением частичного порядка -<. Условие предшествования аг -< а3 понимается как требование расположить прямоугольник а3 выше прямоугольника аг. Алгоритм А^ состоит в последовательном применении алгоритма А2 к подмножествам правильного разбиения списка 5={аг|г = 1,...,п},то есть такого разбиения (5Л) , Л = 1,..., Л , что из аг -< а3, аг € а3 £ 5А" следует 1 < А' < А" < Л. Класс /С^ случайных списков образуется с помощью схемы п последовательных независимых испытаний: предмет аг принимает ширину = IV и высоту — к и помещается в подмножество 5Л" согласно дискретному распределению вероятностей

РюЫа = Рг{т{ = и), кг = к, \ = Л } > О,

для и) = 1,..., IV; к = 1 ,...,#; Л = 1,..., Л;

IV я л

■ш=1 Л=1 А=1

Будем говорить, что список 5 обладает свойством симметричности (асимметричности, регулярности), если им обладает

вектор (р\нх,Р2Нх, ■ ■ ■ ,Р\¥ь.х) для любой пары параметров /г = 1,..., Я; Л = 1,..., А.

Теорема 6 Алгоритм Л^ на ■классе К,* с IV -регулярными случайными списками предметов при

\¥НА/рр = о(п/ 1п п)

является асимптотически точным с оценками

0 (п1пп) ' ^ п/1пп ^ '

где

^ у/ н л

Рр = ууГц ^Р^ > = У^^Р^х ■

ю=1й=1 А=1

Теорема 7 Алгоритм на классе К^ с ]У-асимметричными случайными списками предметов при

УУНА = о(п/\пп)

является асимптотически точным с оценками

Глава 2 посвящена проблемам реализации метода ветвей и границ для задачи упаковки в контейнеры.

В разделе 2.1 рассматривается вопрос представления (кодировки) допустимых решений. В процессе комбинаторного поиска множество кодов задает пространство решений, и исходная задача нахождения оптимального решения сводится к поиску наилучшего элемента (кода) в этом пространстве.

Пространство представлений решений называется Р-допус-тимым2, если оно удовлятворяет следующим требованиям:

1. Пространство кодов конечно.

2. Каждый элемент кода соответствует допустимому решению.

3. Решение задачи может быть получено по его коду за полиномиальное время.

4. Наилучший элемент в пространстве кодов соответствует оптимальному решению исходной задачи.

Доказано, что множество перестановок в сочетании с алгоритмом «следующий пригодный» в качестве декодирующей процедуры определяет Р-допустимое пространство решений. Кроме того, описаны регулярные перестановки, гарантирующее однозначность кода, а также максимальные перестановки, позволяющие не рассматривать заведомо доминируемые упаковки. Это дает основание при реализации метода ветвей и границ ограничиться рассмотрением максимальных регулярных упаковок.

В разделе 2.2 приводятся описание нескольких известных нижних оценок для задачи упаковки в контейнеры и результаты проведенных численных экспериментов по сравнению их эффективности при использовании в методе ветвей и границ.

В третьей главе исследуется задача PSa календарного планирования со складируемыми ресурсами и директивными сроками. Основным результатом главы является

2Murata Н., Fujiyoshi К., Nakatake S., Kajitani Y. VLSI module placement based on rectangle-packing by the sequence-pair// IEEE Trans. Computer-Aided Design. 1996. V. 15. P. 1518-1524

Теорема 8 Решение задачи PSa может быть получено с временной сложностью 0(| Jdirl log Nd + (TV(log/ + log K) + u + N')D), где f — ширина частичного порядка, и — число дуг в графе редукции частичного порядка, К — число видов ресурсов, Jdir — множество работ с директивными сроками, Nj — число различных директивных сроков, N' — суммарное по всем ресурсам число интервалов постоянства функций интенсивности выделения ресурсов, N — суммарное по всем работам и всем ресурсам число интервалов постоянства функций интенсивности потребления ресурсов, D — длина двоичной записи наибольшего директивного срока.

Кроме того, для NP-трудной мультимодальной задачи календарного планирования со складируемыми ресурсами выделен полиномиально разрешимый частный случай, который включает в себя такой практически важный класс задач, когда для всякой работы j и ресурса к задан объем потребления ресурсов bjk и длительности р™ выполнения работы по каждой моде т, причем интенсивность потребления ресурсов для соответствующей моды обратно пропорциональна ее длительности.

Основные результаты диссертации опубликованы в работах:

1. Гимади Э. X., Залюбовский В. В. Асимптотически точный подход к решению одномерной задачи упаковки в контейнеры // Управляемые системы: Сб. научн. тр. Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 25. С. 48-57.

2. Гимади Э. X., Гончаров Е. Н., Залюбовский В. В.

Алгоритм решения задачи сетевого планирование в условиях ограниченных ресурсов // Перспективное планиро-

вание Западно-Сибирского нефтегазового комплекса. Новосибирск: Наука, 1987. С. 172-180.

3. Залюбовский В. В. Вероятностный анализ приближенных алгоритмов для решения задачи линейного раскроя // Тез. докл. конф. «Математическое обеспечение рационального раскроя в системах автоматизированного проектирования». Уфа, 1987. С. 71-72.

4. Гимади Э. X., Залюбовский В. В. Алгоритмы с оценками для задач упаковки и календарного планирования // Тез. докл. III Всесоюзной школы «Дискретная оптимизация и компьютеры». Москва, 1987. С. 96-97.

5. Гимади Э. X., Залюбовский В. В. Задача упаковки в контейнеры: асимптотически точный подход // Известия ВУЗов. Математика. 1997. № 12. С. 25-33.

6. Гимади Э. X., Залюбовский В. В., Шарыгин П. И.

Задача упаковки в полосу: асимптотически точный подход // Известия ВУЗов. Математика. 1997. № 12. С. 34-44.

7. Гимади Э. X., Залюбовский В. В. Эффективно разрешимый класс задач календарного планирования с ограниченными ресурсами // Тез. докл. XII Международной конференции по проблемам теоретической кибернетики. Нижний Новгород, 1999. С. 51.

8. Гимади Э. X., Залюбовский В. В., Севастьянов С. В.

Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций, Сер. 2. 2000. Т. 7, № 1. С. 9-34.

9. Залюбовский В. В. Алгоритм точного решения задачи упаковки в контейнеры // Тез. докл. российской конф. «Дискретный анализ и исследование операций». DA0R'C)4. Новосибирск, 2004. С. 158.

10. Залюбовский В. В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Тр. 13-й Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 2005. Том 1. С. 461-467.

11. Gimadi Е. Kh., Zalyubovsky V. V. Project scheduling with multiple modes: An asymptotically optimal approach // 16th European Conf. on Operations research EURO XVI, Brussels, Belgium, 1998. P. 58-59.

12. Gimadi E. Kh., Zalyubovsky V. V. On some well-solved class of resource constrained project scheduling problem// Symposium on Operations Research SOR'99. Magdeburg, 1999. P. 53.

13. Gimadi E. Kh., Sevastianov S. V., Zalyubovsky V. V.

On the project scheduling problem under stored resource constraints // Proc. 8th IEEE Int. Conference on Emerging Technologies and Factory Automation. Antibes - Juan les Pins, France, 2001. P. 703-706.

14. Zalyubovsky V. V. A new encoding scheme for one-dimensional bin packing // Proc. 2nd Int. Workshop «Discrete optimization methods in production and logistics», Omsk,

2004. P. 194-197

Залюбовский Вячеслав Валерьевич

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 25.01.06. Формат 60x84 1/16. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 43.

Издательство СО РАН 630090, Новосибирск, Морской пр. 2 Филиал "Гео". 630090, Новосибирск, пр. Ак. Коптюга, 3.

297Í

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Залюбовский, Вячеслав Валерьевич

Введение

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 Оценка Ь2.

2.2.3 Класс оценок

2.2.4 Процедура лифтинга и класс оценок L

2.2.5 Результаты вычислительных экспериментов.

3 Задача календарного планирования со складируемыми ресурсами

3.1 Задача календарного планирования.

3.2 Математическая модель.

3.3 Некоторые сведения из теории сетевого планирования и Т-поздние расписания

3.4 Задача PSa и формулировка основного результата.

3.5 Обоснование алгоритма решения задачи PSa на основе Т-поздних расписаний.

3.6 Алгоритм проверки допустимости Т-позднего расписания в задаче PSa.

3.7 Завершение доказательства основной теоремы.

3.8 Полиномиально разрешимый случай задачи MPSа.

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

Диссертация посвящена двум классам задач комбинаторной оптимизации, которые представляют интерес как с точки зрения теории, так и с практической стороны. Несмотря на то, что эти проблемы имеют совершенно различные области приложений, в их математической природе есть немало общего, и многие задачи упаковки можно рассматривать как специальные случаи моделей календарного планирования [44, 48].

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

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

Алгоритм .ЛГ-Р. Первый предмет помещается в первый контейнер. Каждый последующий предмет помещается в тот же контейнер, что и предыдущий, до тех пор, пока в нем достаточно свободного места. В противном случае предмет помещается в новый (пустой) контейнер.

Алгоритм Р\Р. Первый предмет помещается в первый контейнер. Каждый последующий предмет помещается в контейнер, имеющий минимальный индекс из числа тех, которые подходят для его размещения.

Для этих алгоритмов установлены следующие достижимые асимптотические оценки наихудшего поведения: К^р = 2, Ерр = 17/10. Если множество предметов предварительно упорядочить по невозрастанию весов предметов, а затем применить к ним алгоритм N Г или Р'.Р (такие версии алгоритмов обозначаются ИГО и .Р.Р£> соответственно), то оценки улучшаются: = 17/10, = 11/9 [51].

Для задачи упаковки в полосу также был разработан ряд подобных алгоритмов [22, 32, 45]. Один из наилучших на сегодняшний день имеет оценку 5/4 [21]. Более полную информацию об алгоритмах с гарантированными оценками точности можно найти в обзорах [29, 31, 43, 57].

Для задач упаковки в контейнеры и в полосу также известны полиномиальные аппроксимационные схемы (РТАБ) [39] и вполне полиномиальные аппроксимационные темы (РРТАБ) [53, 54].

Решению задач упаковки методами локального поиска посвящены работы [20, 40, 64], а также обзор [49].

В ходе вычислительных экспериментов было установлено, что относительная погрешность алгоритмов типа ./У-Р и «в среднем» существенно отличается от достижимых оценок наихудшего поведения, что стимулировало появление статей, посвященных вероятностному анализу приближенных алгоритмов. Эти работы, как правило, содержат либо оценку отношения математического ожидания числа контейнеров, требуемых некоторым приближенным алгоритмом, к ожидаемому оптимальному числу контейнеров [17, 42, 46, 52, 55], либо описание вероятностных свойств оптимального решения [27, 34, 63, 67]. Обзору различных подходов к вероятностному анализу алгоритмов упаковки посвящена монография [33]

В диссертации для исследования качества приближенного алгоритма используется идея построения алгоритмов с оценками (е, £), предложенная Э. X. Гимади, Н. И. Глебовым и В. А. Перепелицей [7].

Пусть /С — некоторый класс оптимизационных задач. Посредством обозначим оптимальное значение целевой функции для задачи 5 6 /С. Будем считать, что рассматривается задача на минимум и .¿Р*(5) > 0 для всех Я 6Е /С.

Рассмотрим теперь некоторый алгоритм А, который может быть применен к любой задаче 5 класса /С, так что результатом этого применения является допустимое решение задачи 5 со значением целевой функции .Рд(5). При этом, вообще говоря, не исключается, что применение алгоритма Л к некоторым задачам из К может оказаться безрезультатным с точки зрения достижения требуемой точности решения.

Пусть заданы класс задач К, и некоторое семейство V вероятностных мер, определенных на /С. Будем говорить, что алгоритм Л имеет оценки е, относительно V, если для всех Ре?.

Будем рассматривать классы задач, описываемые одним параметром, принимающим в качестве значений натуральные числа. В связи с этим будем далее говорить о классах /Сп задач размерности п, семействах Тп, оценках (б:п, 6п) и их свойствах в зависимости от параметра п.

В качестве примера алгоритма с оценками (еп, 6п) можно привести алгоритм А. А. Боровкова [1] для класса К,п задач коммивояжера, для которых распределения из Тп получаются в результате случайного выбора п точек в ограниченной, односвязной, с достаточно гладкой границей области С? г-мерного евклидова пространства.

Алгоритм А называется. асимптотически точным на классе задач /С, если существуют такие последовательности (£п,6п), что для любого п алгоритм Л удовлетворяет оценкам (еп, 6п) на подмножестве Кп С /С и при этом еп —> 0, 5п —> 0 при п —оо.

Параметры еп и 5п могут трактоваться как оценки относительной погрешности и вероятности несрабатывания алгоритма- соответственно.

Использование техники построения алгоритмов с оценками (еп, <5П) позволило установить условия асимптотической точности малотрудоемких приближенных алгоритмов для решения ряда труднорешаемых задач дискретной оптимизации [3, 4, 8, 9, 10, 13, 18]. Обзор результатов, полученных до 1982 года можно найти в [65].

Задача календарного планирования (ЗКП) является важной частью системы управления проектами. Проект состоит из множества работ, которые необходимо выполнить для достижения предписанной цели. При этом расписание выполнения работ проекта должно удовлетворять целому ряду ограничений, наиболее существенными из которых являются ограничения на объемы выделяемых ресурсов. Традиционно рассматриваются невозобновимые (финансы) и возобновимые (пройзводственные мощности, персонал) ресурсы [66]. Обзор моделей и алгоритмов решения ЗКП приведен в работах [26, 62].

Как отмечено в [44], задача упаковки в контейнеры эквивалентна простейшей задаче календарного планирования с одним ограниченным ресурсом возобновимого типа и единичными длительностями работ при отсутствии ограничений на порядок выполнения работ. На основании этого, в частности, можно сделать вывод об iVP-трудности ЗКП.

В связи с этим интересно исследование сложностного статуса ЗКП при наличии складируемых ресурсов, представляющих собой своеобразный компромисс между возобновимыми и невозобновимыми ресурсами.

Диссертация состоит из введения, трех глав, заключения, списка публикаций автора по теме диссертации и списка литературы.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

Сформулируем основные результаты проведенных исследований.

1. Для задач упаковки в контейнеры и упаковки в полосу предложены полиномиальные алгоритмы для нахождения приближенных решений при случайных входных данных. Установлены условия, при которых эти алгоритмы являются асимптотически точными. Аналогичные результаты получены для задачи упаковки в полосу при задании частичного порядка на множестве пакуемых прямоугольников. Исследована связь задачи упаковки в полосу с частным случаем задачи календарного планирования, для которого также предложен алгоритм нахождения приближенного решения и установлены условия его асимптотической точности.

2. Описан метод представления допустимых решений одномерной задачи упаковки в контейнеры в виде перестановок специального вида. Введено понятие ./У-Р-активных упаковок и показано, что поиск оптимального решения можно вести только в этом классе. Доказано, что каждой перестановке соответствует ровно одна Л^Р-активная упаковка, а при дополнительных условиях на структуру перестановки удается добиться также однозначности обратного соответствия. Кроме того, описан класс максимальных упаковок, использование которого позволяет сократить просматриваемое подмножество допустимых решений в процессе поиска оптимума. Проведено сравнение эффективности различных процедур вычисления нижних оценок в контексте их использования в методе ветвей и границ.

3. Исследована задача календарного планирования с ограниченными ресурсами складируемого типа и директивными сроками. Показано, что понятие складируемых ресурсов не сводимо к традиционно рассматриваемым возобновимым и невозобновимым ресурсам. Предложен полиномиальный алгоритм решения задачи. Для мультимодальной модели календарного планирования выделен частный случай, когда предложенный алгоритм находит оптимальное решение.

Список публикаций автора по теме диссертации

2. Гимади Э. X., Гончаров Е. Н., Залюбовский В. В. Алгоритм решения задачи сетевого планирование в условиях ограниченных ресурсов // Перспективное планирование Западно-Сибирского нефтегазового комплекса. Новосибирск: Наука, 1987. С. 172-180.

6. Гимади Э. X., Залюбовский В. В., Шарыгин П. И. Задача упаковки в полосу: асимптотически точный подход // Известия ВУЗов. Математика. 1997. № 12. С. 34-44.

7. Гимади Э. X., Залюбовский В. В. Эффективно разрешимый класс задач календарного планирования с ограниченными ресурсами // Тез. докл. XII Междунар. конф. по проблемам теоретической кибернетики. Нижний Новгород, 1999. С. 51.

8. Гимади Э. X., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискретный анализ и исследование операций, Сер. 2. 2000. Т. 7, № 1. С. 9-34.

9. Залюбовский В. В Алгоритм точного решения задачи упаковки в контейнеры // Тез. докл. российской конф. «Дискретный анализ и исследование операций». DAOR'04. Новосибирск, 2004. С. 158.

12. Gimadi E. Kh., Zalyubovsky V. V. On some well-solved class of resource constrained project scheduling problem// Symposium on Operations Research SOR'99. Magdeburg, 1999. P. 53.

13. Gimadi E. Kh., Sevastianov S. V., Zalyubovsky V. V. On the project scheduling problem under stored resource constraints // Proc. 8th IEEE Int. Conf. on Emerging Technologies and Factory Automation. Antibes - Juan les Pins, France, 2001. P. 703-706.

14. Zalyubovsky V. V. A new encoding scheme for one-dimensional bin packing // Proc. 2nd Int. Workshop «Discrete optimization methods in production and logistics», Omsk, 2004. P. 194-197

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Залюбовский, Вячеслав Валерьевич, Новосибирск

1. Боровков А. А. К вероятностной постановке двух экономических задач // Докл. АН СССР. 1962. Т. 1, ДО 5. С. 983-986.

2. Боровков А. А. Теория вероятностей. М.: Наука, 1986.

3. Гимади Э. X. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объемами производства // Дискретный анализ и исследование операций, Сер. 2. 2001. Т. 8, № 2. С. 3-16.

4. Гимади Э. X. Обоснование априорных оценок качества приближенного решения задачи стандартизации // Управляемые системы: Сб. научн. тр. Новосибирск: Ин-т математики СО АН СССР, 1987. Вып. 27. С. 12-27.

5. Гимади Э. X. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Новосибирск: Наука, 1988. С. 89-115. (Тр, / АН СССР. Сиб. Отд-ние. Ин-т математики, Т. 10).

6. Гимади Э. X., Глебов Н. И. Экстремальные задачи принятия решений. Уч. пособие. Новосибирск: Новосиб. ун-т, 1982.

7. Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М.: Наука, 1975. Вып. 31. С. 35-42.

8. Гимади Э. X., Глебов Н. И., Сердюков А. И. Алгоритм для приближенного решения задачи коммивояжера и его вероятностный анализ // Сибирский журнал исследования операций. 1994. Т. 1, № 2. С. 8-17.

9. Гимади Э. X., Перепелица В. А. Асимптотически точный подход к решению задачи коммивояжера // Управляемые системы: Сб. научн. тр. Новосибирск: Ин-т математики СО АН СССР, 1974. Вып. 12. С. 35-45.

10. Гимади Э. X., Пузынина Н. М., Севастьянов С. В. О некоторых экстремальных задачах реализации крупных проектов типа БАМ // Экономика и мат. методы. 1979. Вып. 5. С. 1017-1020.

11. Гимади Э. X., Сердюков А. И. Аксиальные задачи о назначениях и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ // Известия ВУЗов. Математика. 1999. № 12. С. 19-25.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М: Мир, 1982.

13. Зуховицкий С. И., Радчик И. А. Математические методы сетевого планирования. М.: Наука, 1965.

14. Козлов М. К., Шафранский В. В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов // Изв. АН СССР. Техническая кибернетика. 1977. № 4. С. 75-81.

15. Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ некоторых алгоритмов упаковки прямоугольников в полосу// Тр. VI Межд. конф. «Дискретные модели в теории управляющих систем», Москва, 7-11 дек. 2004, М., 2004. Р. 178-181.

16. Перепелица В. А., Гимади Э. X. К задаче нахождения минимального гамильтонова контура на графе со взвешенными дугами // Дискретный анализ: Сб. научн. тр. Новосибирск: Ин-т математики СО АН СССР, 1969. Вып. 15. С. 57-65.

17. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

18. Alvim А. С. F., Ribeiro С. С., Glover F., Aloise D. J. A hybrid improvement heuristic for the one-dimensional bin packing problem // J. of Heuristics. 2004. V. 10. P. 205-229.

19. Baker B. S., Brown D. J., Katseff H. P. A 5/4 algorithm for two-dimensional packing // J. of Algorithms. 1981. V. 2, N 2. P. 348-368.

20. Baker B. S., Coffman E. G., Rivest R. L. Orthogonal packings in two dimensions // SIAM J. Computing. 1980. V. 9. P. 846-855.

21. Blazewicz J., Lenstra J. K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity // Discrete Applied Math. 1983. V. 5, N 1. P. 11-24.

22. Bourjolly J. M., Rebetez V. An analysis of lower bound procedures for the bin packing problem // Comput. Oper. Res. 2005. V. 32, N 3. P. 395-405.

23. Böttcher J., Drexl A., Salewski F. Project scheduling under partially renewable resource constraints // Management Sei. 1999. V. 45, N 4. P. 543-559.

24. Brucker P., Drexl A'., Möhring R., Neumann K., Pesch E.

25. Resource-constrained project scheduling: Notation, classification, models, and methods // European J. Oper. Res. 1999. V. 112, N 1. P. 3-41.

26. Coffman E. G., Courcoubetis C., Garey M. R., Johnson D. S., Shor P. W., Weber R. R., Yannakakis M. Perfect packing theorems and the average-case behavior of optimal and online bin packing // SIAM Review. 2002. V. 44, N 1. P. 95-108.

27. Coffman E. G., Downey P. J., Winkler P. Packing rectangles in a strip // Acta Informática. 2002. V. 38, N 10. P. 673-693.

28. Coffman E. G., Galambos G., Martello S., Vigo D. Bin packing approximation algorithms: Combinatorial analysis // Handbook of

29. Combinatorial Optimization. D.-Z. Du, P. M. Pardalos (Eds.). Kluwer Academic Publishers, 1999. P. 151-208.

30. Coffman E. G., Garey M. R., Johnson D. S. An application of bin-packing to multiprocessor scheduling // SIAM J. Comput. 1987. V. 7. P. 1-17.

31. Coffman E. G., Garey M. R., Johnson D. S. Approximation algorithms for bin-packing: A survey // Approximation Algorithms for NP-Hard Problems. D. Hochbaum (Ed.). Boston: PWS Publishing, 1997. P. 46-93.

32. Coffman E. G., Garey M. R., Johnson D. S., Tarjan R. E.

33. Performance bounds for level-oriented two-dimensional packing algorithms // SIAM J. Comput. 1980. V. 9, N 4. P. 808-826.

34. Coffman E. G., Lueker G. S. Probabilistic Analysis of Packing and Partitioning Algorithms. New York: Wiley, 1991.

35. Csirik J, Frenk J. B. G., Galambos G., Rinnoy Kan A. H. G.

36. Probabilistic analysis of algorithms for dual bin packing problems // J. Algorithms. 1991. V. 12. 189-203.35. Data Set 1 for BPP-1. http://www.wiwi.uni-jena.de/Entscheidung/binpp/binldat.htm

37. Dyckhoff H. A typology of cutting and packing problems // European J. Oper. Res. 1990. V. 44. P. 145-159.

38. Eilon S., Christofides N. The loading problem // Management Sei. 1971. V. 17. P. 259-267.

39. Elhedhli S. Ranking lower bounds for the bin-packing problem // European J. Oper. Res. 2005. V. 160, N 1. P. 34-46.

40. Fernandez de la Vega W., Lueker G. S. Bin packing can be solved within l+e in linear time // Combinatorica. 1981. V. 1, N 4. P. 349-355.

41. Falkenauer E. A hybrid grouping genetic algorithm for bin packing // J. Heuristics. 1996. V. 2. P. 5-30.

42. Fekete S., Schepers J. New classes of fast lower bounds for bin packing problems // Math. Program. 2001. V. 91. P. 11-31.

43. Frederickson G. N. Probabilistic analysis for simple one- and two-dimensional bin packing algorithms // Inf. Processing Lett. 1980. V. 11, N 4-5. P. 156-161.

44. Galambos G., Woeginger G. J. Online bin packing — a restricted survey // ZOR — Mathematical Methods of Operations Research. 1995. V. 42. P. 25-45.

45. Garey M. R., Graham R. L., Johnson D. S., Yao A. C.-C.

46. Resource constrained scheduling as generalized bin packing // Journal of Comb. Theory. 1976. V. 21. P. 257-298.

47. Golan I. Performance bounds for orthogonal, oriented two-dimensional packing algorithms // SIAM J. Comput. 1981. V. 10. P. 571-582.

48. Gu X., Chen G., Xu Y. Average-case performance analysis of a 2D strip packing algorithm — NFDH // J. of Combinatorial Optimization. 2005. V. 9, N 1. P. 19-34.

49. Haourari M., Gharbi A. Fast lifting procedures for the bin packing problem // Discrete Optimization. 2005. V. 2. P. 201-218.

50. Hartmann S. Packing problems and project scheduling models: An integrating perspective //J. Oper. Res. Soc. 2000. V. 51. P. 1083-1092.

51. Hopper E., Turton B. C. H. A review of the application of meta-heuristic algorithms to 2D strip packing problem // Artificial Intelligence Review. 2001. V. 16, N 4. P. 257-300.

52. Johnson D. S. Near-optimal bin packing algorithms. Disssertation, Massachusetts Institute of Technology. 1973. Cambridge, Massachusetts.

53. Johnson D. S., Demers A., Ullman J. D., Garey M. R., Graham R. L. Worst-case performance bounds for simple one-dimensional packing algorithms // SIAM J. Comput. 1974. V. 3, N 4. P. 299-325.

54. Karmarkar N. Probabilistic analysis of some bin-packing algorithms // Proc. 23rd Annual Symp. Found. Comp. Sci. 1982. P. 107-111.

55. Karmarkar N., Karp R. M. An efficient approximation scheme for the one-dimensional bin packing problem // Proc. 23rd Annual Symp. Found. Comp. Sci. 1982. P. 312-320.

56. Kenyon C., Remila E. A near optimal solution to a two-dimensional cutting stock problem // Mathematics of Operations Research. 2000. V. 25, N 4. P. 645-656.

57. Knodel W. A bin packing algorithm with complexity 0(n log n) and performance 1 in the stochastic limit // Lect. Notes Comput. Sci. 1981. V. 118. P.369-377.

58. Kolish R. Project scheduling under resource constraints // Efficient heuristics for several problem classes. Heidelberg: Physica, 1995.

59. Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey // European J. Oper. Res. 1992. V. 141. P. 241252.

60. Lueker G. S. Bin packing with items uniformly distributed over intervals a, 6] // Proc. 23rd Annual Symp. Found. Comp. Sei. 1982. P. 289-297.

61. Martello S, Toth P. Knapsak Problems. Chichester: Wiley, 1990.

62. Martello S., Toth P. Lower bounds and reduction procedures for the bin packing problem // Discrete Appl. Math. 1990. V. 28. P. 59-70.

63. Rhee W. T., Talagrand M. Optimal bin packing with items of random sizes III // SIAM J. Comput. 1989. V. 18, N 3. P. 473-486.

64. Scholl A., Klein R., Jürgens C. BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem // Comput. Oper. Res. 1997. V. 24. P. 627-645.

65. Slominski L. Probabilistic analysis of combinatorial algorithms: a bibliography with selected annotations // Computing. 1982. V. 28, N 3. P. 257-267.

66. Slowinski R. Two approaches to problems of resource allocation among project activities: A comparative study // Journal of the Operational Society. 1980. V. 31. P. 711-723.

67. Talagrand M. Expected wasted space of optimal simple rectangle packing// Probab. Theory Relat. Fields. 2005. V. 131. P. 145-153.

68. Tarjan R. E. Data Structures and Network Algorithms. Philadelphia: SIAM, 1983.

69. Valerio de Carvalho J. M. Exact solution of bin-packing problems using column generation and branch-and-bound // Annals of Operations Research. 1999. V. 86. P. 629-659.

70. Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems // Math. Program. 1999. V. 86. 565-594.