Методы принятия оптимальных решений на основе анализа эффективности значений функции цели в задачах прямоугольной упаковки тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Месягутов, Марат Артурович

• Месягутов, Марат Артурович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Месягутов, Марат Артурович

Символика и обозначения.

Введение

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

1.1 Задача одномерной упаковки.

1.2 Задача двухмерной упаковки.

1.3 Задача продолженного одномерного раскроя.

1.4 Численный эксперимент.

1.5 Выводы.

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

2.1 Математические модели.

2.2 Сокращение размерности задачи.

2.3 Ветвления. . ;.

2.4 Нижние границы.

2.5 Точный алгоритм.

2.6 Численный эксперимент.

2.7 Выводы.■.

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

3.1 Кодирование и декодирование ортогональной упаковки.

3.2 Л-окрестность допустимой упаковки.

3.3 Нижняя граница в Л-окрестности

3.4 Поиск лучшего локально оптимального решения с использованием Л-окрестностей . :.

3.5 Численный эксперимент . . ;.

3.6 Выводы.

Результаты и выводы.

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

Введение диссертации (часть автореферата) на тему «Методы принятия оптимальных решений на основе анализа эффективности значений функции цели в задачах прямоугольной упаковки»

Актуальность темы. Диссертация посвящена одному из прикладных разделов исследования операций, задачам раскроя-упаковки, непосредственно связанных с системным анализом. Этот класс задач представляет большой интерес как с точки зрения теории, так и с практической стороны. Рассматриваемые задачи принадлежат к J\fV-трудным проблемам. Точные методы позволяют решать эти задачи с небольшим количеством предметов, а приближенные методы слабо структурированы и, по мнению многих ученых, перспективным направлением для их решения является системных подход.

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

В силу того, что рассматриваемые задачи являются ЛЛР-трудными в сильном смысле, практический интерес представляет построение быстрых алгоритмов поиска локально оптимального решения, близкого по значению глобальному оптимуму. К сожалению, приближённые методы не дают ответа на вопрос насколько экономно расходуется материал. Однако, „близость" приближённого решения к оптимальному может быть оценена с помощью нижней границы для значения целевой функции.

С теоретической стороны интерес представляет построение улучшенных нижних границ и точных методов для повышения размерности решаемых задач. Однако, поиск нижней границы зачастую представляет собой так же AfV-трудную проблему. Что касается точных методов решения, то продвижение на этом пути осуществляется очень медленно. Для приближённого решения задачи большую роль играет вычисление локальной нижней границы при оценке окрестностей допустимых решений, что позволяет организовать процесс принятия решений для поиска локального оптимума, направленный на достижение рационального решения, подходящего с точки зрения промышленности по критерию оценки отклонения от оптимума.

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

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

Для достижения цели работы были поставлены и решены следующие задачи:

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

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

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

4. Реализация предложенных методов на ЭВМ и проведение анализа их эффективности. Исследование качества полученной нижней границы. Выделение области применимости разработанных методов.

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

На защиту выносятся:

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

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

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

4. Численное исследование эффективности предложенных методов и качества новых нижних границ и решений задачи двухмерной упаковки.

Научная новизна. Новыми в работе являются:

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

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

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

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

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

Программная реализация полученного приближённого метода для задачи двухмерной упаковки показала преимущества перед известными приближёнными алгоритмами на широком классе задач, что подтверждено расчетами. Это делает программную реализацию метода практически применимой в реальных производственных ситуациях. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано в ВНТИЦ, свидетельство №50200601233.

Апробация работы. Работа выполнялась в рамках научной школы по раскрою-упаковке УГАТУ, при финансовой поддержке РФФИ, грант №10-07-91330-HHUOa, гранта на исследования Германской службы академических обменов (DAAD), стипендии Georgius-Agricola Саксонского министерства наук и искусства, и Европейского исследовательского гранта Erasmus Mundus. Результаты работы и её разделы докладывались и обсуждались на следующих конференциях и семинарах:

1. 3-я и 4-я Всероссийская конференция „Проблемы оптимизации и экономические приложения", Омский филиал института математики им. Соболева СО РАН, г. Омск, 2006, 2009 года.

2. Всероссийская конференция „Математическое программирование и приложения", институт математики и механики УрО РАН, г. Екатеринбург, 2007 год.

3. 5-ая Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. ЛАкуила, Италия, 2008 год.

4. 14-ый Юговосточный немецкий коллоквиум (Siidostdeutsches Kolloqui-um), г. Лейпциг, Германия, 2008 год.

5. 18-ый Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Кёнигштейн, Германия, 2008 год.

6. 6-ая Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. Валенсия, Испания, 2009 год.

7. 13-ый Симпозиум международной федерации автоматики (International federation of automatic control, IFAC) по проблемам управления информацией в промышленном производстве, г. Москва, 2009 год.

8. Международная школа-конференция для студентов, аспирантов и молодых ученых „Фундаментальная математика и ее приложения в естествознании", Б ГУ, г. Уфа, 2005, 2009 года.

9. Международный симпозиум по информатике и информационным технологиям (International Workshop on Computer Science and Information Technologies, CSIT), г. Карлсруэ, Германия, г. Уфа, 2006, 2009 года.

10. 19-ый Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Хольцхау, Германия, 2010 год.

11. Региональная зимняя школа-семинар аспирантов и молодых ученых факультета Информатики и Робототехники УГАТУ, г. Уфа, 2007 год.

12. Семинары института вычислительной математики Дрезденского Технологического Университета, г. Дрезден.

13. Семинары кафедры вычислительной математики и кибернетики УГАТУ, г. Уфа.

14. Семинары кафедры математики УГАТУ, г. Уфа.

15. Семинар института математики с вычислительным центром Уфимского научного центра РАН, г. Уфа.

Публикации. По теме диссертации автором опубликовано 15 работ, в том числе три работы в рецензируемых журналах, рекомендованных ВАК.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Месягутов, Марат Артурович

3.6 Выводы

Предложен и реализован одноточечный метод локального поиска оптимума. Рекордные допустимые решения определяются в Л-окрестности и улучшаются при переходе к другой Л-окрестности. При этом на текущей итерации эволоционного алгоритма реализуется NF-стратегия для различных списков 7г, различающихся перестановками пассивных элементов. Приведены численные результаты сравнения предложенного алгоритма с другими эффективными алгоритмами. HSS-Л показал на болыпенстве классов лучшие результаты. При этом видны пути его совершенствования: применение метода с запретами при поиске в окрестности; использование других метаэвристик, генетического алгоритма и метода отжига. Кроме того, перспективы имеет гибридизация точного метода и эвристики. Среднее отклонение решений от нижней гранцы, предложенной A. Bortfeld, равно 1,38%, т.е. меньше чем отклонение 1,94% от точного решения задачи 1СВРР, полученные тем же алгоритмом.

Результаты и выводы

В заключении сформулируем основные результаты исследований и выводы.

1. Разработан метод поиска глобальной нижней границы для задачи двухмерной упаковки, который сводится к оптимальному решению задачи одномерной продолженной упаковки. Метод отличается тем, что позволяет находить нижнюю границу с улучшенным значением по сравнению с ранее известными [103] и, следовательно, доказать оптимальность для большего числа задач.

2. Разработан точный метод решения задачи одномерной продолженной упаковки, который основан на использовании правила „следующий подходящий" и оценок, получаемых с помощью решения вспомогательной задачи линейного программирования. Доказана точность метода. Предложены и обоснованы новые критерии доминантности и правила отсечения. Разработана новая стратегия ветвлений при поиске верхней границы для значения целевой функции. Это позволяет существенно сократить переборный процесс. Разработанный метод позволяет решать в ограниченное время & 42% задач из открытой библиотеки оптимально.

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

4. Предложенные методы реализованы на ЭВМ. Результаты экспериментов показали, что существуют классы задач, на которых методы имеют различную результативность. Проведён анализ эффективности методов на различных классах задач и выделена область применимости разработанных методов. Это позволяет априорно сделать выбор лучшей схемы решения по классу рассматриваемых задач. Исследовано качество полученной нижней границы. Результаты экспериментов показали, что разработанная нижняя граница не хуже известных для задач из открытой библиотеки и для 37% задач удалось существенно улучшить значение нижней границы по сравнению с известными результатами.

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

1] В.М. Картак, М.А. Месягутов, Э.А. Мухачева и А.С. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика, 6: 167-180, 2009. •

2] М.А. Месягутов. Задача двухмерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки // Информационные технолргии, 6: 13-23, 2010.

3] М.А. Месягутов. Точный метод поиска оптимума задачи одномерной продолженной упаковки // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета, 3: 130-134, 2010.

4] М.А. Месягутов, Э.А. Мухачева, Г.Н. Белов и Г. Шайтхауэр. Упаковка одномерных контейнеров с продолженным выбором идентичных предметов: точный метод поиска оптимального решения // Автоматика и ' Телемеханика, 2010. Принята в цечать.

5] М.А. Месягутов. Поиск локальных оптимумов в задачах раскроя-упаковки с использованием локальных границ // Интеллектуальные системы обработки информации и управления. Сборник статей 2-ой региональной зимней школы-семинара аспирантов и молодых ученых, Уфа, 1: 22-24, 2007.

6] Zhitnikov V.P., Philippova A.S., and М.А. Mesyagutov. Projecting of orthogonal packing based on slice-structures // Proceeding of the Workshop on Computer Science and Information Technologies, Karlsruhe, 2: 131-134, 2006.

7] Э.А. Мухачева, М.А. Месягутов и А.С. Филиппова. Эволюционный алгоритм (1+1)-ЕА с локальной нижней границей для задач прямоугольной упаковки полосы // III Всероссийская конференция "Проблемы оптимизации и экономические приложения". Материалы конференции, Омск, 1: 114, 2006.

8] М.А. Месягутов и А.С. Филиппова. Задачи ортогональной упаковки: поиск решений в окрестностях с локальной нижней границей // Информационный бюллетень Ассоциации математического программирования, Екатеринбург, 11: 219, 2007.

9] М.А. Mesyagutov, G. Scheithauer, and G. Belov. A branch & bound approach for the ID contiguous cutting-stock problem // 5th Euro special interest group on cutting and packing (ESICUP) meeting. Collected papers, L'Aquila, 1: 20, 2008.

10] M.A. Mesyagutov, G. Scheithauer, and G. Belov. LP-based exact approach for the ID contiguous cutting-stock problem // 18th Workshop on discrete Optimization. Collected papers, Konigstein, P. 19-21, 2008.

11] M.A. Mesyagutov, G. Scheithauer, and G. Belov. Exact approaches for the ID contiguous cutting-stock 'problem // 6th Euro special interest group on cutting and packing (ESICUP) meeting. Collected papers, Valencia, 1: 33-34, 2009.'

12] M.A. Месягутов и Мухачева Э.А. Точный метод решения задачи одномерной упаковки с продолженным выбором идентичных предметов //IV Всероссийская конференция "Проблемы оптимизации и экономические приложения". Материалы конференции, Омск, 1: 150, 2009.

13] М.А. Mesyagutov, V.M. Kartak, and R.S. Valeev. Lower bounds for the 2D strip packing problem: linear and ID contiguous relaxation // Preprints of the 13th IFA.C Symposium on Information Control Problems in Manufacturing (INCOM), Moscow, P. 2003-2007, 2009.

14] M.A. Mesyagutov. LP-based exact approach for the ID contiguous cutting-stock problem // Proceeding of the Workshop on Computer Science and Information Technologies (CSIT), Crete, 1: 280-281, 2009.

15] M.A. Mesyagutov and G. Scheithauer. Branch-and-price algorithms for the ID contiguous bin packing problem // 19th Workshop on discrete Optimization, Holzhau, P. 37-40, 2010.

16] M.A. Месягутов'и А.С. Филиппова. Решение задачи двухмерной прямоугольной упаковки объектов в полубесконечную полосу алгоритмом (1+1)-ЕА блочной структуры с использованием локальной нижней границы. Программа для ЭВМ. Регистрационный номер №50200601233. Всероссийский научно-технический информационный центр (ВНТИЦ).

Список литературы диссертационного исследования кандидат физико-математических наук Месягутов, Марат Артурович, 2010 год

1. L.V. Kantorovich. Mathematical methods of organizing and planning production (translation of the paper of 1939) // Management Science. 1960. 6(4): 366-422.

2. P.C. Gilmore, R.E. Gomory. A linear programming approach to the cutting-stock problem // Operations Research. 1961. 9(6): 849-859.

3. A.H. Land, A.G. Doig. An automatic method of solving discrete programming problems // Econometrica. 1960. 28(3): 497-520. '

4. J.M. Valerio de Carvalho. LP models for bin packing and cutting stock problems // European Journal of Operational Research. 2002. 141: 253-273.

5. G. Belov. Problems, models.and algorithms in one- and two-dimensional cutting. PhD thesis. Dresden University of Technology. 2003.

6. Jl.В. Канторович, В.А. Залгаллер. Расчет рационального раскроя промышленных материалов. Лениздат. 1951.

7. S. Martello, P. Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. NY, USA. 1990.

8. O. Marcotte. The cutting stock problem and integer rounding // Mathematical Programming. 1985. 33: 82-92.

9. O. Marcotte. An instance of the cutting stock problem for which the rounding property does not hold // Operations Research Letters. 1986. 4/5: 239-243.

10. J. Rietz, G. Scheithauer. Tighter bounds for the gap and non-irup constructions in the one-dimensional cutting stock problem // Optimization. 2002. 51.6: 927-963.

11. G. Scheithauer, J. Terno. The modified integer round-up property of theone-dimensional cutting stock problem // European Journal of Operationalt, \

12. Research. 1995. 84: 562-571.

13. F. Vanderbeck. On dantzig-wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm // Operations Research. 2000. 48: 111-128. •

14. P. Vance. Branch-and-price algorithms for the one-dimensional cutting stock problem // Computational Optimization and Applications. 1998. 9(3): 212— 228.

15. J.M. Valerio de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound // Annals of Operational Research. 1999. 86: 629-659.

16. J.F. Shapiro. Dynamic programming algorithms for the integer programming // Operations Research. 1968. 16(1): 103-121.

17. R.K. Ahuja, T.L. -Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. 1993.

18. G. Wascher, T. Gau. Heuristics for the integer one-dimensional cutting stock problem: a computational study // OR Spektrum. 1996. 18: 131-144.

19. F. Vanderbeck, L. Wolsey. An exact algorithm for ip column generation /■/ Operations Research Letters. 1996. 19(4): 151-159.

20. C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W. Savelsbergh, P.H. Vance. Branch-and-price: Column generation for solving huge integer programs // Operations Research. 1996. 46: 316-329.

21. Z. Degraeve, L. Schrage. Optimal integer solution to industrial cutting stock problems // INFORMS Journal on Computing. 1999. 11: 406-419.

22. F. Vanderbeck. Computational study of a column generation algorithm for binpacking and cutting stock problems // Mathematical Programming. 1999. 86: 565-594.

23. И.В. Романовский, Н.П. Христова. Решение дискретных минимаксных задач методом дихотомии // Журнал Вычислительной Матиматики и Математической Физики. 1973. 13(5): 1200-1209.

24. С.В. Карцев. Об одном классе дискретных минимаксных задач // Ки-бирнетика. 1979. 5: 139-141.

25. И.В. Романовский. Алгоритмы решения экстремальных задач. М.: Наука. 1977.

26. A. Scholl, R. Klein, G. Juergens. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem // Computers and Operational Research. 1997. 24(7): 627-645.

27. D. Simchi-Levi. New worst case results for the bin-packing problem // Naval Research Logistics. 1994. 41: 579-585.

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

29. Э.А. Мухачева, А.Ф. Валеева. Метод динамического перебора в задаче двухмерной упаковки // Информационные технологии. 2000. 5: 30-37.

30. J.M. Valerio de Carvalho. Using extra dual cuts to accelerate column generation // INFORMS Journal on Computing. 2005. 17(2): 175-182.

31. E.A. Mukhachevaj V.A. Zalgaller. Linear programming cutting problems /./1.ternational Journal of Software Engineering and Knowledge Engineering. 1993, 3: 463-476.

32. E. Aarts, J. Lenstra. Local search in combinatorial optimization. John Wiley & Sons, Inc. NY, USA. 1997.

33. Ю.А. Кочетов. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и её приложения: Сборник лекций молодежных и научных школ по дискретной математике и её приложениям. 2000. pages 87-117.

34. Е.Е. Bischoff, M.D. Marriott. A comparative evaluation of heuristics for container loading // European Journal of Operational Research. 1990. 44(2): 267-276.

35. Батищев Д.Ю. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: Воронежский гос. техн. ун-т. 1995.

36. Е. Falkenauer. A hybrid grouping genetic algorithm for bin packing // Journal of Heuristics. 1998. 33(1): 5-30.

37. F. Glover. Tabu search and adaptive memory programming advances, application and challenges // Interfaces in Computer Science and Operations Research. 1996. pages 1-75.

38. Yu. Kochetov, A. Usmanova. Probabilistic tabu search with exponential neighborhood for the bin packing problem. In Proceedings MIC'2001. pages 619-624. 2001. .

39. F. Loris. An application of simulated annealing to the cutting stock problem // European Journal of Operational Research. 1999. 144(3): 542-556.

40. H. Foerster, G. Wascher. Simulated annealing for order spread minimization in sequencing cutting patterns // European Journal of Operational Research. 1998. 110(2): 272-281.

41. П.А. Борисовский. Исследование эволюционных алгоритмов решения некоторых задач дискретной оптимизации. PhD thesis. Омский филиал Института математики им. С. JI. Соболева СО РАН, Омск. 2005.

42. А.С. Филиппова. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологий блочных структур / / Информационные технологии. 2006. 6: Приложение (32 страницы).

43. П.А. Борисовский, А.В. Еремеев. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. 3: 3-9.

44. JI.B. Канторович, В.А. Залгаллер. Рациональный раскрой промышленных материалов. Новосибирск: Наука. 1971.

45. Р. С. Gilmore, R. E. Gomory. Multistage cutting stock problem of two and more dimensions // Operations Research. 1965. 13(1): 94-120.

46. J.E. Beasley. An exact two-dimensional non-guillotine cutting tree search procedure // Operations Research. 1985. 33(1): 49-64.

47. J.E. Beasley. Bounds for two-dimensional cutting // Journal of the Operational Research Society.' 1985. 36(1): 71-74.

48. M. Padberg. Packing small boxes into a big box // Mathematical Methods of Operations Research. 2000. 52(1): 1-21.

49. J. Terno, R. Lindemann, G. Scheithauer. Zuschnittprobleme und ihre praktische Losung. Verlag Harry Deutsch, Thun und Frankfurt/Main; Fachbuchverlag, Leipzig. 1987.

50. Ю.Г. Стоян, С.В. Яковлев. Математические модели и оптимизационныечметоды геометрического проектирования. Киев: Наукова думка. 1986.

51. Yu. Stoyan, М. Novozhilova. Non-guillotine placement of rectangles into a strip of given width // Pesquisa Operational. 1999. 19(2): 189-211.

52. Yu. Stoyan, A. Pankratov. Regular packing of congruent polygons on the rectangular sheet // European Journal of Operational Research. 1999. 113: 653-675.

53. А.И. Липовецкий. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. 1985. pages 80-87.

54. В.В. Бухвалова. • Задача прямоугольного раскроя: метод зон и другие алгоритмы. С.Пб.: Государственный университет. 2001.

55. М. Kenmochia, Т. Imamichia, К. Nonobeb, М. Yagiurac, Н. Nagamochia. Exact algorithms for the two-dimensional strip packing problem with andwithout rotations // European Journal of Operational Research. 2009. 198(1): 73-83.

56. S. Martello, D. Vigo. Exact solution of the two-dimensional finite bin packing problem // Management Science. 1998. 44: 388-399.

57. G. Wascher, P. Schwerin. A new lower bound for the bin-packing problem and its integration to MTP // Pesquisa Operational. 1999. 19(2): 111-131.

58. M.A. Boschetti. The two-dimensional finite bin packing problem //A Quarterly Journal of Operations Research. 2003. 1(1): 27-42.

59. Э.Х. Гимади, В.В. Залюбовский, И.П. Шарыгин. Задача упаковки в полосу: асимптотически точный подход // Известия высших учебных заведений. Математика. 1997. 12(427): 34-44.

60. D. Liu, Н. Teng. An improved bl-algorithm for genetic algorithm of the orthogonal packing of rectangles // European Journal of Operational Research. 1999. 112(2): 413-420. •

61. A. Bortfeld, H. Gehring. Applying tabu search to container loading problem // Operations Research Proceedings. 1998. pages 533-538.

62. Э.А. Мухачева, А.С. Мухачева, A.B. Чиглинцев, M.A. Смагин. Задачи двухмерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения // Информационные Технологии. 2001. Приложение №9.

63. Э.А. Мухачева, А.С. Мухачева, Д.В. Чиглинцев. Генетический алгоритм блочной структуры в задачах двухмерной упаковки // Информационные технологии. 1999; 11: 13-18.

64. И.П. Норснков. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. 1: 2-7.

65. S. Imahori, M. Yagiura, T. Ibaraki. Local search algorithms for the rectangle packing problem with general spatial costs // Mathematical Programming. 2003. pages 543-569.

66. P. Chen, Y. Chen, M. Goel, F. Mang. Approximation of two-dimensional rectangle packing. Technical report. 1999.

67. E. Hopper, B. Turton. A review of the application of meta-heuristic algorithms to 2D strip packing problems // Artificial Intelligence Review. 2001. 16(4): 257-300.

68. D. Pisinger. • Heuristics for the container loading problem // European Journal of Operational Research. 2002. 141(2): 382-392.

69. Ю. Кочетов, H. Младенович, П. Хансен. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. 2003. 10(1): 11-43.

70. М. Monachi. Algorithms for packing and scheduling problems. PhD thesis. University of Bologna. 2001. •

71. S. Martello, M. Monachi, D. Vigo. An exact approach to the strip-packing problem // INFORMS Journal on Computing. 2003. 15(3): 310-319.

72. S. Fekete, J. van der Veen. Two-dimensional strip packing in reconfigurable computing. In 2nd ESICUP (Euro Special Interest Group on Cutting and Packing) Meeting-, Southampton. 2005.

73. Э.А. Мухачева, А.С. Мухачева. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. 2: 10-15.

74. F. Clautiaux, A. Jouglet, J. Carlier, A. Moukrim. A new constraint programming approach for the orthogonal packing problem // Computers and Operations Research. 2008. 35(3): 944-959.

75. S. Fekete, J. Schepers. New classes of lower bounds for bin packing problems. In Mathematical Programming, pages 257-270. Springer. 1998. •

76. S.P. Fekete, J. Schepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60(2): 311-329.

77. B.M. Картак, М.А. Месягутов, Э.А. Мухачева, А.С. Филиппова. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. 6: 167-180.

78. В.П. Житников, А.С. Филиппова. Задача прямоугольной упаковки в полубесконечную полосу: поиск решения в окрестности локальной нижней границы // Информационные технологии. 2007. 5: 55-62.

79. S. Hartmann. Project Scheduling under limited resources. Models, methods and applications. Springer, Berlin. 1999.

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

81. G. Belov, G. Scheithauer. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of Operational Research. 2002. 141(2): 274-294.

82. G. Belov, G. Scheithauer, E.A. Mukhacheva. One-dimensional heuristics adapted for two-dimensional rectangular strip packing // The Journal of the Operational Research Society. 2008. 59(6): 823-832.

83. Э.А. Мухачева, Д.А. Назаров. Конструирование прямоугольных упаковок: алгоритм перестройки на базе блочных структур // Автоматика и телемеханика. 2008. 2: 97-113.

84. Н. Murata, К. Fujiyoshi, S. Nakatake, Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence-pair // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1996. 15(12): 1518-1524.

85. K.S. Booth, G.S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using p'q-tree algorithms // Journal of Computational Systems Science. 1976. 13: 335-379.

86. B.B. Залюбовский. Точные и асимптотически точные алгоритмы для задач упаковки и календарного планирования. PhD thesis. Институт математики им. С. JI. Соболева СО РАН, Новосибирск. 2006.

87. A. Bortfeld. A genetic algorithm for the two-dimensional strip packing problem with rectangular prices // European Journal of Operational Reseach. 2006. 172(3): 814-837.

88. J.O. Berkey, P.Y. Wang. Two dimensional finite bin packing algorithms // Journal of Operational Research Society. 1987. 38: 423-429.

89. R. Baldacci, M. Boschetti. • A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem // European Journal of Operational Research. 2007. 183: 1136-1149.

90. S. Fekete, J. Sthepers. A general framework for bounds for higher-dimensional orthogonal packing problems // Mathematical Methods of Operations Research. 2004. 60:'311-329.

91. A. Lodi, М. Martello, D. Vigo. Recent advances on two-dimensional bin packing problems // Discrete Applied Mathematics. 2002. 123(1-3): 379-396.

92. Э.А. Мухачева, Д.А. Назаров, A.C. Филиппова. Проектирование прямоугольных упаковок с использованием декодеров блочной структуры // Автоматика и телемеханика. 2006. 6: 161-173.

93. В.В. Залюбовский. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Тр. XIII Байкальской международной шк.-семинара. Иркутск. 2005. 1: 461-466.