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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ

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

Вяткина Кира Вадимовна

ПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ РАЗМЕЩЕНИЙ ПРЯМОУГОЛЬНИКОВ

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

Санкт-Петербург 2004

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского Государственного Университета.

Научные руководители:

доктор физико-математических наук, профессор Романовский Иосиф Владимирович кандидат физико-математических наук, доцент Бухвалова Вера Вацлавовна

Официальные оппоненты:

доктор физико-математических наук, профессор Сушков Юрий Акимович кандидат физико-математических наук, доцент Новиков Федор Александрович

Ведущая организация:

Уфимский государственный авиационный технический университет

Защита диссертации состоится и \ о " ы^ои*_ 2004 года

в № часов на заседании диссертационного совета Д 212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан 2004 года.

Ученый секретарь диссертационного совета

доктор физико-математических наук Б. К. Мартыненко

профессор

Общая характеристика работы

Актуальность темы. В современной комбинаторной оптимизации важное место занимают задачи прямоугольного раскроя, ортогональной упаковки и теории расписаний. Эти три класса задач тесно связаны между собой: задачей об упаковке называют обобщение задачи (плоского) раскроя для пространств размерности d > 3, а задачи планирования при ограниченныхресурсах могут быть интерпретированы в терминах задач ортогональной упаковки [3, 4, 5, 8]. Интерес к данным задачам объясняется, в частности, их большой практической значимостью.

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

Таким образом, одним из актуальных направлений в данной области является исследование комбинаторных свойств размещений [4, 5, 10] и их последующее использование при решении указанных задач.

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

Научную новизну работы составляют перчисленные ниже основные результаты; они же являются предметом защиты.

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

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

пространства.

♦ Доказана NP-трудность задачи об оптимальной упаковке прямоугольников с заданной наклонной нумерацией в полосу фиксированной ширины. Получено обобщение данного результата для пространства размерности d > 2.

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

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

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

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

Апробация работы. Результаты диссертации докладывались и обсуждались на трех международных конференциях: на Конференции SIAM по геометрическому дизайну и вычислениям (SIAM GD'03, Сиэтл, США), на Первом семинаре группы ESICUP - European Special Interest group in Cutting and Packing (1st ESICUP Meeting, Лютер-штадт Виттенберг, Германия, март 2004), и на 20-м Европейском се-

минаре по вычислительной геометрии (БигоСО'04, Севилья, Испания, март 2004), а также на XXVI Конференции молодых ученых (механико-математический факультет МГУ, апрель 2004).

Публикации. По теме диссертации опубликовано четыре работы [11, 12, 13, 14], список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав и заключения (в нумерации глав введение и заключение имеют соответственно номера 1 и 5). Диссертационная работа изложена на 75 страницах машинописного текста; при этом объем основного текста составляет 67 страниц. Диссертация содержит 36 рисунков. Список литературы содержит 70 наименований.

Содержание работы

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

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

В разделе 1.2 введены понятия зоны прямоугольника и графа размещения, а также сформулированы их основные свойства. Используемая в работе терминология заимствована из [9].

Условимся для прямоугольникар обозначать его левую нижнюю вершину через Ар, левую верхнюю - через В, правую верхнюю -через Ср, правую нижнюю - через Dp. Зоной Z(p) прямоугольникар будем называть открытый левый нижний квадрант, построенный из точки Ср (рис. 1а).

Сопоставим размещению R ориентированный граф GR, не содержащий петель. Каждому прямоугольнику из R соответствует вершина графа; две различные вершиныр и s соединяются дугой (р, s), если pf]Z(s) -ф 0 (рис. 1b). Будем называть GR графом размещения. В 1988 г. А. И. Липовецким [10] была доказана следующая теорема.

Рис. 1: а) Прямоугольникр и его зона Z(p). Ь) Размещение прямоугольников и соответствующий ему граф размещения.

Теорема 1. Любое топологическое упорядочение вершин графа GR индуцирует нумерацию ^ прямоугольников из R, для которой

ЧреВ.: и{^(д)|/я(<?) < /й(р)} Пр = @. (*)

В разделе 1.3 приведено формальное описание моделей вычислений, которые впоследствии будут использованы для оценки временной сложности алгоритмов: это так называемая веществен-нозначнаяравнодоступная адреснаямашиная [7] и модель деревьев сравнений [6].

Раздел 1.4 содержит описание структуры основной части диссертационной работы.

Во второй главе рассматривается задача о разделении размещения на отдельные прямоугольники путем рекурсивного применения угловых разрезов. Угловой разрез на плоскости образован двумя лучами - горизонтальным и вертикальным — с общим началом. Мы зафиксируем направления обоих лучей: горизонтальный луч всегда будет направлен влево, а вертикальный - вниз. Пусть О - их общее начало; будем говорить, что данный разрез построен из точки О. Далее мы ограничимся рассмотрением угловых разрезов, построенных из правых верхних вершин прямоугольников (см. рис. 2).

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

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

В разделе 2.2 доказано существование разделяющей последовательности угловых разрезов для произвольного размещения прямоугольников. Оно вытекает из теоремы 1: такую последовательность индуцирует нумерация 1Я (рис. 2).

Рис. 2: Пример разделяющей последовательности угловых разрезов для размещения Я, индуцированной нумерацией 1Г

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

Задача ПОСЛЕДОВАТЕЛЬНОСТЬ УГЛОВЫХ РАЗРЕЗОВ. Дано размещение Я прямоугольников на плоскости. Требуется построить для Я разделяющую последовательность угловых разрезов.

Теорема 2. Нижняя оценка сложности задачи ПОСЛЕДОВАТЕЛЬНОСТЬ УГЛОВЫХ РАЗРЕЗОВ составляет П(пк^п), где

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

С учетом результатов, изложенных далее в главе 4, может быть сформулирована следующая теорема.

Теорема 3. Для размещения Я прямоугольников, разделяюшая последовательность угловых разрезов может быть построена за оптимальное времяQ{n\ogn) при затратах памятиО(п), где п = |Л|.

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

Гофром называется простой ортогональный многоугольник, монотонный по отношению к прямой у = - х (рис. За). Прямоугольник, очевидно, является частным случаем гофра.

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

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

Теорема 4. Любое размещение Р гофров может быть разделено на отдельные гофры посредством зигзагообразных разрезов, каждый из которых совпадает с границей зоны одного из гофров.

Теорема 5. Для размещения Р гофров, разделяющая последовательность угловыхразрезовможет быть построена за оптимальное время 0(п1с^п) при затратах памяти О(п), где п - суммарное количество вершин всех гофров из Р.

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

На рис. 4а£ изображен угловой разрез в трехмерном пространстве.

Размещение параллелепипедов, приведенное на рис. 4с, не может быть разделено на два (непустых) подмножества при помощи

Ь) .

Рис. 3: а) Гофр; Ь) зигзагообразный разрез.

Рис. 4: a), b) Две - из 8 возможных - ориентации углового разреза в трехмерном пространстве, с) Пример размещения параллелепипедов, которое не может быпь разделено посредством угловых разрезов произвольной ориентации

углового разреза, даже если мы допускаем разрезы произвольной ориентации (т. е. любой из 8 возможных).

В третьей главе рассматривается задача построения графа размещения.

В разделе 3.1 для случая плоскости предложен оптимальный алгоритм, основанный на методе плоского заметания (Описание метода плоского заметания может быть найдено в [1, 2, 7j).

Теорема 6. В случае плоскости, граф GR, размещения прямоугольников R может бить построен за время 0(nlogn + |J5r|) приза-тратах памяти 0{п+ |-Бд|), где п = |Д|, a |.£7r| - число дуг GR. Такой алгоритм оптимален в рамках модели деревьев сравнений.

Далее в том же разделе указана возможность модификации предложенного алгоритма для случая гофров.

Теорема 7. Граф GPразмещения гофровРможет быть построен за время 0(nlogn + n\Ep\) при затратах памяти 0{п+\Ец\), где п = |R| - суммарное количество вершин всех гофров из Р, а \Ер\ -число дуг GP.

В разделе 3.2 предложены два алгоритма построения графа размещения в пространстве размерности d > 2. В основе этих алгоритмов лежит общий подход: мы сводим задачу построения графа размещения к задаче регионального поиска [1, 7].

Теорема 8. Пусть R -размещение ё-боксов. Граф размещения GR может, быть построен за время <9(п2_з + |£д|) при затратах памяти 0(п + |-Ед|), где п =\Щ, - с использованием кё-деревьев как вспомогательной структуры данных для выполнениярегиональных запросов.

Теорема 9. Пусть R - размещение ё-боксов. Граф размещения GR может быть построен за время 0{уь\о^~х п+\Еп\) призатратах памяти п + |.Ел|), где п = |Я|, - с использованием рас-

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

Глава 4 посвящена вопросам существования и эффективного построения наклонной нумерации для размещений.

Будем называть нумерацию 1К для размещения прямоугольников R наклонной, если для любой прямой I с неотрицательным тангенсом угла наклона номера прямоугольников, пересекаемых I, возрастают вдоль I (рис. 5).

Рис. 5: Пример размещения прямоугольников и соответствующей ему наклонной нумерации. Прямая I последовательно пересекает прямоугольники с номерами 1, 3, 5, 7.

В разделе 4.1 доказывается существование наклонной нумерации для произвольного размещения прямоугольников. Для этого мы показываем эквивалентность свойства, лежащего в основе ее определения, свойству (*) нумерации 1К из условия теоремы 1.

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

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

Задача ПОСТРОЕНИЕ НАКЛОННОЙ НУМЕРАЦИИ. Дано размещение R прямоугольников на плоскости. Требуется построить для R наклонную нумерацию IR.

Теорема 10. Нижняя оценка сложности задачи ПОСТРОЕНИЕ НАКЛОННОЙ НУМЕРАЦИИ составляется,logn), где п = \R\.

Теорема 11. Для размещения R прямоугольников, наклонная нумерация может быть построена за оптимальное время&(п logn) при затратах памяти О(п).

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

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

В разделе 4.5 указан способ модификации алгоритма построения наклонной нумерации для размещений гофров.

Теорема 12. Для размещения Р гофров, наклонная нумерация может быть построена за оптимальное время 0(n logn) при затратах памяти О(п), где п = |R| - суммарное количество вершин всех гофров из Р.

В разделе 4.6 приведено обобщение понятия наклонной нумерации для пространств старших размерностей.

Рассмотрим множество векторов 0,1 < г < d}, где e - единичные векторы, направленные вдоль осей координат. Нумерация IR для размещения R из d-боксов является наклонной, если для любой прямой l, для которой 3v 6 V : J||v, номера боксов, пересекаемых l, возрастают вдоль l.

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

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

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

В разделе 4.7 показана NP-трудность задачи об упаковке в полосу (Strip Packing Problem) прямоугольников с заданной наклонной нумерацией (sloping Enumeration).

Задача SPPE-2. Дано множество прямоугольников Р с фиксированной нумерацией /р и горизонтальная полоса высоты II. Требуется определить минимальную длину L полосы, при которой можно упаковать в полосу все прямоугольники из Р таким образом, чтобы нумерация Ir была наклонной для результирующего размещения прямоугольников.

Теорема 13. Задача SPPE-2NP-трудна.

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

Задача SPPE-d. Дано множество d-боксов Р с фиксированной нумерацией /р и контейнер, размеры W... , Wd которого также зафиксированы. Требуется определить минимальную длину W\ контейнера, при которой можно упаковать в него все боксы из Р таким образом, чтобы нумерация IP была наклонной для результирующего размещения.

Теорема 14. Задача SPPE-d NP-трудна.

Задача SPPE-2 может быть переформулирована для гофров. Очевидно, что при этом она останется NP-трудной, так как прямоугольник является частным случаем гофра.

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

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

Список литературы

[1] М. de Berg, M. van Kreveld, M. Overmars, О. Schwarzkopf. Compuatational Geometry: Algorithms and Applications. Second Edition. Springer-Verlag Berlin Heidelberg, 2000.

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

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

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

[5] 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)

[6] D. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Reading. Massachusetts: Addison-Wesley, 1998. Пер. с англ.: Д. Кнут. Искусство программирования, том 3: Сортировка и поиск. Второе издание. Издательский дом "Вильяме", 2000.

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

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

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

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

Работы автора по теме диссертации

[11] V. Bukhvalova, К. Vyatkina. An optimal algorithm for partitioning a set of rectangles with right-angled cuts. In SIAM Conference on Geometric Design and Computing. Abstracts, p. 34, Seattle, USA, November 2003.

[12] K. Vyatkina, V. Bukhvalova. On separating boxes with right-angled cuts. In 1st ESICUP Meeting. Abstracts, p. 11, Lutherstadt Wittenberg, Germany, March 2004.

[13] K. Vyatkina. On geometric properties of enumerations of axis-parallel rectangles. In J.M. Diaz-Bdfiez, A. Marquez, J.R. Portillo (eds), Proc. 20th European Workshop on Computational Geometry; pages 163-166, Seville, Spain, March 24-26, 2004.

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

ЛР № 040815 от 22.05.97.

Подписано к печати 27.04.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 п.л. Тираж 100 экз. Заказ 3243. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

90 14

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.

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

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

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

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

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 с.