автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метод поиска с запретами для задач упаковки в контейнеры

Введение

Глава 1. Постановка задачи упаковки в контейнеры и обзор методов ее решения

1.1 Классификация задач раскроя-упаковки

1.2 Постановка задачи, оценка сложности решения

1.3 Методы решения задачи ВРР

1.3.1 Эвристические алгоритмы полиномиальной сложности

1.3.2 Асимптотически точные и точные алгоритмы

1.3.3 Метаэвристические алгоритмы

1.4 Выводы

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

2.1 Многообразие недетерминированных подходов

2.2 Вероятностные простые эвристики

2.2.1 Алгоритм «случайная перестановка с равными вероятностями»

2.2.2 Алгоритм «случайная перестановка с параметром»

2.2.3 Алгоритм «случайный контейнер с параметром»

2.2.4 Общая характеристика простых вероятностных алгоритмов

2.2.5 Численный эксперимент с алгоритмами RPEP, RPP, RBP

2.2.5.1 Описание тестовых задач

2.2.5.3 Определение параметров алгоритма RBP

2.2.5.2 Определение параметров алгоритма RPP

2.2.5.4 Сравнение вероятностных алгоритмов

2.3 Алгоритм локального спуска

2.3.1 Описание алгоритма

2.3.2 Численный эксперимент с детерминированным и вероятностным алгоритмами локального спуска

2.4 Выводы

Глава З.Метод поиска с запретами 48 3.1 Общая схема метода

3.1.1 Классическая структура метода поиска с запретами

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

3.1.2.1 Общий алгоритм решения

3.1.2.2 Конкретизация метода поиска с запретами

3.2 Окрестности соседних решений полиномиальной мощности

3.2.1 Контейнерно-ориентированное представление решения и операторы его преобразования

3.2.2 Рандомизированные окрестности

3.3 Оценочная функция

3.4 Список запретов

3.4.1 Различные структуры списка запретов

3.4.2 Управление длиной списка

3.5 Процедуры диверсификации и интенсификации

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

3.7 Выводы

Глава 4. Экспоненциальная окрестность соседних решений

4.1 Постановка задачи о назначениях и методы ее решения

4.2 Модификация метода TS с использованием задачи о назначениях

4.2.1 Алгоритмы построения экспоненциальной окрестности решений

4.2.2 Улучшение начального решения

4.2.3 Процедура диверсификации

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

4.5 Выводы 89 Заключение 90 Литература 91 Приложение

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

Актуальность темы исследования. Актуальность проблемы создания эффективных алгоритмов для задачи упаковки обусловлена как широким практическим применением задач раскроя-упаковки (Р-У) в различных отраслях производства, так и многообразием постановок задач Р-У, трудностью создания адекватных математических моделей и выбора методов их решения. Задачи Р-У представляют собой важный раздел задач дискретной оптимизации и исследования операций. В рамках решения этих задач исследуются общий проблемы, характерные для указанных областей математики.

Сложность решения задач Р-У обусловлена их принадлежностью к классу NP-трудных задач комбинаторной оптимизации. Исследуемая задача является NP-трудной в сильном смысле, так как содержит в качестве подзадачи также NP-трудную задачу. В настоящее время не существует точных методов полиномиальной сложности для их решения. Большинство исследователей склоняется к мнению, что NP^P, то есть упомянутые точные методы в принципе не могут быть разработаны.

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

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

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

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

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

4. Описание математической модели экспоненциальной окрестности решений, разработка метаэвристического алгоритма, сочетающего локальный поиск по различным окрестностям решений.

5. Проведение и анализ результатов численного эксперимента на базе созданного программного обеспечения.

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

1. Математические модели задачи упаковки в контейнеры, оценка мощности пространства решений.

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

3. Алгоритм поиска с запретами по полиномиальным окрестностям соседних решений.

4. Метод построения экспоненциальной окрестности решений с использованием задачи о назначениях.

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

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

Апробация работы. Результаты работы и отдельные ее разделы докладывались и обсуждались на международной научной конференции «Проблемы оптимизации и экономические приложения» (1997г., Омск); на международной молодежной научно-технической конференции «Интеллектуальные системы управления и обработки информации» (1999 г., Уфа); на XII Байкальской международной конференции (2001г.,Иркутск); на первой всероссийской научно-практической конференции по вопросам решения оптимизационных задач в промышленности «Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного прокетирования» (2001 г., Санкт-Петербург).

Основные результаты работы:

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

2. Вычислены оценки мощности множества допустимых решений задачи

3. Разработаны и исследованы вероятностные алгоритмы решения задачи

4. Предложен алгоритм поиска с запретами, использующий две полиномиальные окрестности. Проведено исследование компонентов алгоритма

5. Разработан метод построения экспоненциальной окрестности решений и алгоритм поиска решений в ней с полиномиальной сложностью

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

7. Разработанные алгоритмы программно реализованы. Проведены численные эксперименты, подтверждающие перспективность данного подхода.

Заключение

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

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

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

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

1. Барлыбаев Р.Х., Мухачева А.С., Усманова А.Р. Исследование эффективности алгоритмов распределения одномерного ресурса. // Проблемы оптимизации и экономические приложения. Материалы международной научной конференции. -Омск, 1997. -С. 24.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.:Наука,1965.-458 с.

3. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу. Дискретные задачи оптимизации. // Управляемые системы., выпуск 25,-Новосибирск, 1984.-С.17-37.

4. Габитов В.А. Розанова Л.Ф., Усманова А.Р. Предоптимизационный анализ задач гильотинного двумерного раскроя.// Принятие решений в условиях неопределенности. Межвузовский научный сборник. -Уфа, 1999. -С. 78-82.

5. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Новосибирск, 1991.-С.29-33.

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

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

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

9. Гончаров Е.Н., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. // Дискретный анализ и исследование операций, Сер.2, Т.6, №1,1999.- С. 12-32.

10. Ю.Диниц Е.А., Кронрод М.А. Один алгоритм решения задачи о назначениях. // Доклады Академии наук СССР. Том 189, № 1,2,3; 1969. С.23-25.

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

12. Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации.// Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ.- М.:МГУ, 2001.- С.87-117.

13. Кочетов Ю.А. Вероятностные алгоритмы локального поиска для задач дискретной оптимизации.// Материалы Сибирской конференции по исследованию операций. Новосибирск, 1998.- С. 2124.

14. Кочетов Ю.А., Усманова А.Р. Вероятностный поиск с запретами для задачи упаковки в контейнеры. / / Сборник докладов XII Байкальской международной конференции. -Иркутск,2001.- С.22-27.

15. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. -Уфа, 1998.-216 с.

16. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ.- М.: Машиностроение, 1984.-176 с.

17. Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя. Информационные технологии.-М.:2001,№6.-С.24-32.

18. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука,1987.- 274с.

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

20. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. -М.: Мир, 1985.-512 с.

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

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

23. Усманова А.Р. Вероятностные жадные эвристики для задачи упаковки в контейнеры.// Сборник докладов 0птим-2001. Первая всероссийская научно-практическая конференция по вопросам решения оптимизационных задач в промышленности.-Спб,2001 .-С.141-145.

24. Усманова А.Р. Применение метаэвристик в интеллектуальной системе линейного раскроя.// Интеллектуальные системы управления и обработки информации. Материалы международной молодежной научно-технической конференции. -Уфа, УГАТУ, 1999.- С. 97.

25. Approximation algorithms for NP-hard problems/ D.S. Hochbaum, editor. PWC, 1997-P.525.

26. Blazewicz , Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. // Annals of OR, 41(1-4), 1993.-pp.315-325.

27. Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems Part I. //Discrete Applied Mathematics, Vol.65,1996,-pp.97-122.

28. Brucker P.,. Hurink J., Werner F. Improving local search heuristics for some scheduling problems Part II. //Discrete Applied Mathematics, Vol.72,1997.-pp.47-69.

29. Coffman E.G., Garey M.R., Johnson D.S. Approximation algorithms for bin-packing.- An updated surey. //Algorithm Design for Computer System Design. CISM courses and lectures, No 284, 1984.- pp.49-106.

30. Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco. 1979 -324 p.

31. Gilmore P.C. and Gomory R.E. A linear programming approach to the cutting stock problem. // Oper. Res., No 9,196l.-pp.948-959.

32. Gilmore P.C. and Gomory R.E. A linear programming approach to the cutting stock problem Part II. //Oper. Res., Nol 1,1963.-pp.863-888.

33. Glover F. Tabu search wellsprings and challenges. EJOR, Vol.106, 1998.-pp.221-225.

34. Glover F. Tabu search.- Part I. // ORSA Journal on Computing, No 1,1989.-pp.190-206.

35. Glover F. Tabu search.- Part II. // ORSA Journal on Computing, No 2,1990.-pp.4-32.

36. Glover F., Laguna M. Tabu search in modern heuristic techniques for combinatorial problems.- Blackwell Publishing, 1992.-75p.

37. Glover F., Taillard E., de Werra D. A user's guide to tabu search.// Annals of Operation research. -Vol. 41,1993.- pp.3-28.

38. Gutin G. Exponential neighborhood local search for the traveling salesman problem.// Comput. Oper. Res. Vol.26, 1999,- pp. 313-320.

39. Dyckhoff H. A typology of cutting and packing problems.// EJOR, Vol.44, 1990.- pp.145-159.

40. Falkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing. Journal of Heuristics, Vol.2, No 1,1996,- pp.5-30.

41. Foerster H., Wascher G. Simulated Annealing for order spread minimization in sequencing cutting patterns.// EJOR, Vol. 110, 1998.-pp.272-281.

42. Fredericson G.N. Probabilistic analysis for simple one- and two-dimensional bin packing algorithms.// Information Processing Letters, Vol.11, No 4-5, 1980.-pp.156-161.

43. Hubscher R., Glover F. Applying Tabu Search with influential diversification to multiprocessor scheduling.// Computers Ops.Res., Vol. 21, No 8, 1994.-pp.877-884.

44. Johnson D.S., Demers A., Ullman J.D., Garey M.R., Graham R.L. Worst-case performance bounds for simple one dimensional packing algorithms. // SI AM J. Comput., Vol.3, No 4,1974,- pp.229-325.

45. Khan L.R. An exchange heuristic for the bin packing problem. Presented at 14th Conference of IFORS, 1996.

46. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles.// EJOR, Vol. 112, 1999.-pp.413-420.

47. Martello S.,Toth P. Knapsack Problems, Algorithms and Computer Implemetations. John Wiley and Sons Ltd.- England, 1990.

48. Nowicki E., Smutnicki C. The flow shop with parallel mashines: A tabu search approach.//EJOR, V.106, 1998.-pp.226-253.

49. Rhee W.T., Talagrand M. Optimal bin packing with items of random sizes. //SI AM J. Comput., Vol.18, No 3, 1989.-pp.473-486.

50. Schcithauer G., Terno I. The modified integer round-up property of the one-dimensional cutting stock problem.//EJOR, Vol.84,1999.-pp.563-571.

51. Scholl A., Klein R., Jurgens C. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem.// Computers Ops.Res. Vol. 24, No 7, 1997.-pp. 627-645.

52. Schwerin P., Wacher G. The Bin-Packing Problem: A problem Generator and Some Numerical Experiments with FFD Packing.// International Transactions in Operational Research.V.4,5/6,1997.- pp.337-389.

53. Vasilyeva L.I., Usmanova A.R. The one-dimensional cutting problem: exact and heuristic algorithms. // Problem of Technology Transfer. International Scientific-Technical Workship.-Ufa, 1999.-pp.214-216.

54. Verhoeven M.G.A. Tabu search for resourse-constrained scheduling. // EJOR, Vol.106, 1998.-pp.266-276.

55. Woodruff D.L. Proposals for chunking and Tabu Search. //EJOR, Vol.106, 1998.-pp.585-598.