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

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

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

Введение

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. Исследована задача календарного планирования с ограниченными ресурсами складируемого типа и директивными сроками. Показано, что понятие складируемых ресурсов не сводимо к традиционно рассматриваемым возобновимым и невозобновимым ресурсам. Предложен полиномиальный алгоритм решения задачи. Для мультимодальной модели календарного планирования выделен частный случай, когда предложенный алгоритм находит оптимальное решение.

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

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. Залюбовский В. В Алгоритм точного решения задачи упаковки в контейнеры // Тез. докл. российской конф. «Дискретный анализ и исследование операций». DAOR'04. Новосибирск, 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. 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

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

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.