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

• Вяткина, Кира Вадимовна
• кандидат физико-математических наук
• 2004

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

1 Введение

1.1 Задачи раскроя, упаковки и теории расписаний

1.1.1 Классификация задач раскроя.

1.1.2 Классификация задач упаковки .7.

1.1.3 Задачи ортогональной упаковки.

1.1.4 Задачи планирования при ограниченных ресурсах

1.2 Размещения и графы.

1.2.1 Граф размещения на плоскости.

1.2.2 Граф многомерного размещения.

1.3 Модели вычислений.

1.4 Структура работы.

2 Разделение размещения прямоугольников посредством угловых разрезов

2.1 Размещения, содержащие вырожденные прямоугольники

2.2 Существование разделяющей последовательности разрезов

2.3 Нижняя оценка сложности

2.4 Построение разделяющей последовательности разрезов

2.5 Обобщение для гофров

2.6 Трехмерный случай.

3 Построение графа размещения

3.1 Плоский случай.

3.1.1 Алгоритм построения графа размещения.

3.1.2 Доказательство оптимальности.

3.1.3 Обобщение для гофров

3.2 Случай ¿-мерного пространства

3.2.1 Задача регионального поиска.

3.2.2 Два метода построения графа размещения.

4 Наклонная нумерация для размещений прямоугольников

4.1 Существование.

4.2 Построение.

4.2.1 Нижняя оценка сложности

4.2.2 Оптимальный алгоритм.

4.2.3 Обоснование корректности

4.2.4 Обработка вырожденных случаев.

4.3 Минимальный и максимальный номер прямоугольника

4.4 Взаимнооднозначные соответствия.

4.5 Обобщение для гофров

4.6 Обобщение для пространств высших размерностей.

4.6.1 Нумерация без повторений.

4.6.2 Нумерация с повторениями.

4.7 Задача об упаковке полосы.

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

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

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

1.1 Задачи раскроя, упаковки и теории расписаний

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

Данная задача допускает естественное обобщение на случай пространств высших размерностей. В пространстве размерности с1 > 3 соответствующую задачу называют обычно "задачей об упаковке рюкзака". Сразу отметим, что некоторые задачи теории расписаний могут быть переформулированы в терминах задач многомерной упаковки.

Впервые задача оптимального раскроя была сформулирована Л. В. Канторовичем в 1939 г. в его брошюре "Математические методы организации и планирования производства" [54], ставшей впоследствии знаменитой.

Очень важное значение для развития данной тематики имела опубликованная в 1961 г. работа [22] П. С. Гилмора (Р. С. СПтоге) и Р. Е. Го-мори (II. Е. Сотогу), в которой был предложен подход к решению задачи раскроя, основанный на методе линейного программирования.

Практическое значение задач раскроя и упаковки чрезвычайно велико; широта спектра их применений может быть наглядно проиллюстрирована нижеследующим списком, приведенным А. С. Мухачевой в ее диссертационной работе [60]:

• задача раскроя запаса материала;

• задача плотного размещения геометрических объектов в заданной области;

• задача загрузки рюкзака;

• задача упаковки ящиков (контейнеров);

• задача загрузки транспорта;

• задача выбора ассортимента;

• задача планировки помещений;

• задача обеспечения ритмичности производственного процесса;

• задача распределения памяти вычислительной машины;

• задача составления расписания многопроцессорных систем.

Заключение диссертации по теме «Теоретические основы информатики», Вяткина, Кира Вадимовна

5 Заключение

В диссертации получены следующие основные результаты:

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

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

• Рассмотрена задача об оптимальной упаковке прямоугольников с заданной наклонной нумерацией для полосы фиксированной ширины. Показано, что эта задача является КР-трудной. Получено обобщение данного результата для пространства размерности в, > 2.

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

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

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

Все предложенные в диссертации алгоритмы реализованы в экспериментальном программном прототипе.

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

1. Р. К. Agrawal. Minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts. European Journal of Operational Research., 64(3) :410—422, 1993.

2. A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analisys of Computer Algorithms. Addison-Wesley, 1976. Пер. с англ.: A. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

3. J. Е. Beasley. Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36:297-306, 1985.

4. J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of ACM, 18:509-517, 1975.

5. J. L. Bentley. Decomposable searching problems. Inform. Process. Lett., 8:244 251, 1979.

6. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Compuatational Geometry: Algorithms and Applications. Second Edition. Springer-Verlag Berlin Heidelberg, 2000.

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

8. V. Bukhvalova, L. Faina. Rectangular cutting layout problem. http://loris.dipmat.unipg.it/usa/index.html, 1998.

9. V. Bukhvalova, K. Vyatkina. An optimal algorithm for partitioning a set of rectangles with right-angled cuts. In: SIAM Conference on Geometric

10. Design and Computing. Program and Abstracts, p. 34, Seattle, USA, November 2003.

11. Т. H. Cormen, Ch. E. Leiserson, R. L. Eivest. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1990. Пер. с англ.: Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

12. И. F. R. К. Chung, М. R. Garey, D. S. Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic Discrete Methods, 3:66-76, 1982.

13. E. G. Coffman Jr., M. R. Garey, D. S. Johnson. Approximation algorithms for bin-packing an updated survey. In G. Ausiello, N. Lucertini and. P. Serafini (eds), Algorithm Design for Computer System Design, 49-106, Springer, Vienna, 1984.

14. E. G. Coffman Jr., P. W. Shor. Average case analysis of cutting and packing in two dimensions. European Journal of Operational Research, 44(2):134-144, 1990.

15. D. Dobkin, R. Lipton. On the complexity of computations under varying set of primitives. Journal of Computer and System Sciences, 18:86-91, 1979.

16. H. Dyckhoff. A Typology of Cutting and Packing Problems. European Journal of Operational Research, 44(2):145 159, 1990.

17. H. Dyckhoff, U. Finke. Cutting and Packing in Production and Distribution: A Typology and Bibliography. Springer-Verlag, Berlin, 1992.

18. L. Faina. An application of simulated annealing to the cutting stock problem. European Journal on Operational Research, 114(3):542-556, 1999.

19. S. P. Fekete, J. Schepers. New classes of lower bounds for the bin packing problem. Mathematical Programming, 91:11-31, 2001.

20. S. P. Fekete, J. Schepers. A combinatorial characterization of higher-dimensional orthogonal packing. http://arxiv.org/abs/cs.DS/0310032, 2003.

21. S. P. Fekete, E. Koehler, J. Teich. Higher-dimensional packing with order constraints. http://arxiv.org/abs/cs.DS/0308006, 2003. (submitted to SIAM Journal of Computing)

22. M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: Freeman, 1979. пер. с англ. M. П. Гэри , Д. С. Джонсон. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1987. -272с.

23. Р. С. Gilmore, R. Е. Gomory. A linear programming approach to the cutting stock problem. Operations Research, 9:848-859, 1961.

24. E. Hadjiconstantinou, N. Christofides. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, 83(l):39-56, 1995.

25. R. M. Karp. Reductibility among combinatorial problems. In R.E. Miller and J. W. Thatcher (eds), Complexity of Computer Computations, pages 85-103, Plenum Press, New York, 1972.

26. D. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Reading, Massachusetts: Addison-Wesley, 1998.

27. Н. Т. Kung, F. Luccio, F. P. Preparata. On finding the maxima of a set of vectors. Journal of the ACM 22(4):469-476, Oct. 1975.

28. D. T. Lee, С. K. Wong. Quintary trees: a file structure for multidimensional database systems. ACM Trans. Database Syst., 5:339353, 1980.

29. G. S. Lueker. A data structure for orthogonal range queries. In Proc. 19th. Annu. IEEE Sympos. Found. Comput. Set., pages 28-34, 1978.

30. S. Martello, P. Toth. Knapsack Problem: Algorithms and Computer Inmplementations. Wiley, 1990.

31. В. B. Mohanty, K. Mathur, N. J. Ivancic. Value considerations in three-dimensional packing A heuristic procedure using the fractional knapsack problem. European Journal of Operational Research, 74(1):143-151, 1994.

32. R. H. Möhring, A. S. Schulz, F. Stork, M. Uetz. Solving Project Scheduling Problems by Minimum Cut Computations. Technical Report 680-2000, TU Berlin, 2000.

33. J. O'Rourke. Computational Geometry in C. Second Edition. Cambridge University Press, 1998.

34. M. Padberg. Packing small boxes into a big box. Mathematical Methods of Operations Research, 52:1-21, 2000.

35. F. P. Preparata, M. I. Shamos. Computational Geometry: An Introduction. Springer Verlag, New York, 1985. Пер. с англ.: Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. Москва, "Мир", 1989.

36. М. О. Rabin. Proving simaltenious positivity of linear forms. Journal of Computer and System Sciences, 6:639 650, 1972.

37. E. M. Reingold. On the optimality of some sets of algorithms. Journal of the ACM, 19:649-659, 1972.

38. J. Riehme, G. Scheithauer, J. Terno. The solution of two-stage guillotine cutting stock problems having extremely varying order demands. European Journal of Operational Research, 91(3):543 552, 1996.

39. Y. Stoyan, G. Yaskov, G. Scheithauer. Packing of various radii solid shperes into a parallelepiped. Preprint MATH-NM-17-2001, TU Dresden, 2001.

40. Y. Stoyan, G. Scheithauer, D. Pridatko, T. Romanova, M. Gil. Phi-functions for primary 3D-objects. Preprint MATH-NM-15-2002, TU Dresden, November 2002.

41. Y. Stoyan, J. Terno, G. Scheithauer, M. Gil, T. Romanova. Construction of a Phi-function for two convex polytopes. Applicationes Mathematicae 29.2:199-218, 2002.

42. A. G. Tarnowski, J. Terno, G. Scheithauer. A polynomial time algorithm for the guillotine pallet loading problem. INFOR 32:275-287, 1994.

43. K. Vyatkina. On geometric properties of enumerations of axis-parallel rectangles. In: J. M. Diaz-Banez, A. Marquez, J. R. Portillo (eds), Proc. 20th European Workshop on Computational Geometry, pages 163-166, Seville, Spain, 2004.

44. K. Vyatkina, V. Bukhvalova. On separarting boxes with right-angled cuts. In: 1st ESICUP Meeting. Program and Abstracts, p. 11, Lutherstadt Wittenberg, Germany, March 2004.

45. J. Weglarz. Project Scheduling. Recent Medels, Algorithms and Applications. Kluwers Academic Publishers, Norwell, MA, USA, 1999.

46. D. E. Willard. Predicate-oriented database search algorithms. PhD. thesis, Aiken Comput. Lab., Harvard Univ., Cambridge, MA, 1978. Report TR-20-78.

47. D. E. Willard. The super b-tree algorithm. Report TR-03-79, Aiken Comput. Lab., Harvard Univ., Cambridge, MA, 1979.

48. M. Wottawa. Struktur und algorithmische Behandlung von praxisorientiren dreidimensionalen Packungs-problemen. Ph.D. thesis, Universität zu Köln, 1996.

49. В. В. Бухвалова. Реализация метода зон Липовецкого для прямоугольного раскроя. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования.: Тезисы докл. всесоюзной конференции, 16-17, Уфа, 1987.

50. В. В. Бухвалова. Использование языка геометрического моделирования в прямоугльном раскрое. Математическое обеспечение рационального раскроя в САПР: Материалы конференции, 80-87, Уфа, 1988.

51. В. В. Бухвалова. Задача прямоугольного раскроя: метод зон и другие алгоритмы. Санкт-Петербург: НИИХ СПбГУ, 2001.

52. В. В. Бухвалова, К. В. Вяткина. О построении графа размещения. Тезисы XXVI Конференции молодых ученых, механико-математический факультет МГУ, 33-34, апрель 2004.

53. А. Д. Вайнштейн. Задачи об упаковке прямоугольников в полосу, (обзор) Управляемые системы. ИМ СО АН СССР, вып. 25, 17-37, 1984.

54. С. Ю. Дремин, В. А. Залгаллер. О раскрое листа на равные прямоугольные заготовки. Оптимизация (Новосибирск), 27/44:136-142, 1981.

55. Л. В. Канторович. Математические методы организации и планирования производства. Л.: Изд-во Ленингр. ун-та, 1939.

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

57. С. Д. Кузнецов. Методы сортировки и поиска. http://www.citforum.ru/programming/tlieory/sorting/sorting2.shtml, 2003.

58. А. И. Липовецкий. К оптимизации свободного размещения прямоугольников. Автоматизация проектирования в машиностроении, 80-87, Минск: НТК АН БССР, 1985.

59. А. И. Липовецкий. Свойства прямоугольных укладок. Препринт, УрО АН СССР, Институт машиностроения, Свердловск, 1988.

60. А. И. Липовецкий. Алгоритмы негильотинного прямоугольного раскроя. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тезисы докл. всесоюзной конференции, 72-79, Уфа, 1988,

61. А. С. Мухачева. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. Диссертация на соискание ученой сетпени к. ф. м. н., Уфимский государственный авиационный технический университет, 1999.

62. Э. А. Мухачева. Поиск рационального решения в двухкритери,-алъной задаче гильотинного раскроя. Оптимизация (Новосибирск), 33/50, 1983. 56-62.

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

64. Э. А. Мухачева. Основные тенденции развития автоматизированного поектирования гильотинного раскроя. Математическое обеспечение рационального раскроя в САПР: Материалы конференции, 20-23, Уфа, 1988.

65. Ф. А. Новиков. Дискретная математика для программистов. Изд. Питер, 2000. -304с.

66. И. В. Романовский. Решение задач гильотинного раскроя методом переработки списка состояний. Кибернетика, 11:102-103, 1969.

67. И. В. Романовский. Оптимальный раскрой одномерного сырья случайной длины. Исследование операций и статистическое моделирование, 2:97 102, С.-Петербургский гос. ун-т, 1974.

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

69. И. В. Романовский. Дискретный анализ. Третье издание, переработанное и дополненное. ВНУ, Невский диалект, 2003. -320 с.

70. Ю. Г. Стоян, Н. И. Гиль. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наукова думка, 1976. -144 с.

71. Ю. Г. Стоян, В. Я. Винарский, В. Н. Абаляев. Регулярное размещение геометрических объектов в ограниченных областях. Харьков ИПмаш, 1990. -24 с.