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

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

Гильотинная резка особенно распространена в стекольной промышленности. Листы стекла надрезаются по горизонтальным и вертикальным линиям, а затем ломаются по этим линиям для получения более мелких панелей. [1] Она также полезна для резки стальных пластин, резки деревянных листов для изготовления мебели и резки картона на коробки. [2]

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

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

Терминология и предположения

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

  • Большой прямоугольник , также называемый листом заготовки , представляет собой необработанный прямоугольный лист, который следует разрезать. Он характеризуется шириной W 0 и высотой H 0 , которые являются основными входными данными для задачи
  • Маленькие прямоугольники , также называемые элементами , являются требуемыми выходами резки. Они характеризуются шириной w i и высотой h i и для i в 1,..., m , где m — количество прямоугольников. Часто допускается наличие нескольких прямоугольников одинаковых размеров; в этом случае пара размеров ( w i , h i ) часто называется типом .
  • Шаблон для резки , часто называемый просто шаблоном , представляет собой расположение небольших прямоугольников на листе заготовки. Он может быть задан как последовательность точек ( x i , y i ), для i в диапазоне 1,..., m , где ( x i , y i ) — нижняя левая координата прямоугольника i . В таком шаблоне прямоугольник i занимает горизонтальный сегмент ( x i , x i + w i ) и вертикальный сегмент ( y i , y i + h i ).
  • Сборка относится к построению нового прямоугольника путем присоединения двух меньших прямоугольников. Из-за ограничения гильотины существует только два типа сборок: в горизонтальной сборке объединенный прямоугольник имеет ширину w i + w j и высоту max( h i , h j ); в вертикальной сборке объединенный прямоугольник имеет ширину max( w i ,w j ) и высоту h i + h j . Каждый шаблон может быть представлен как рекурсивная последовательность сборок. Каждая рекурсивная последовательность сборок соответствует многим различным шаблонам, которые имеют эквивалентную комбинаторную структуру; набор всех шаблонов, соответствующих одной и той же рекурсивной сборке, называется классом гильотины-резки . [4]

Некоторые проблемы принимают дополнительные входные данные, как описано ниже. Цель состоит в том, чтобы вырезать из исходного прямоугольника несколько меньших прямоугольников с целевыми размерами. Часто делаются следующие предположения: [2]

  • Все разрезы имеют нулевую ширину. Это не сильно снижает общность, поскольку если каждый разрез имеет фиксированную ширину d >0, то задачу можно свести к варианту с нулевой шириной, просто добавив d к w i и h i для i в 0,..., m .
  • Целевые размеры не могут быть повернуты, т. е. w -by- h не тот же тип, что и h -by- w . Это не сильно теряет в общности, так как вариант, в котором прямоугольники могут быть повернуты, может быть сведен к невращаемому варианту путем явного добавления повернутых шаблонов.

Проверка заданного шаблона

В задаче проверки шаблона есть шаблон разрезания, заданный как последовательность точек ( x i , y i ), для i из 1,..., m , где ( x i , y i ) — нижняя левая координата прямоугольника i (имеется один прямоугольник каждого целевого измерения). Цель состоит в том, чтобы решить, можно ли реализовать этот шаблон, используя только разрезы гильотины, и если да, то найти последовательность таких разрезов.

Очевидное необходимое условие состоит в том, что никакие два входных прямоугольника не перекрываются в обоих измерениях. Бен Мессауд, Ченгбин и Эспинус [5] представляют более сильное условие, которое является как необходимым, так и достаточным. Входные прямоугольники упорядочены слева направо, так что x 1 ≤ ... ≤ x m . Существует перестановка p индексов, такая что при этой перестановке прямоугольники будут упорядочены снизу вверх, т. е. y p (1) ≤ ... ≤ y p ( m ) . При наличии четырех индексов i 1 ≤ i 2 и j 1 ≤ j 2 множество E( i 1 , i 2 , j 1 , j 2 ) содержит индексы всех прямоугольников, нижний левый угол которых находится в прямоугольнике [ x i 1 , x i 2 ] X [ y p ( j 1) , y p ( j 2) ]. Схема резки является схемой гильотины тогда и только тогда, когда для всех четверок индексов i 1 ≤ i 2 и j 1 ≤ j 2 выполняется по крайней мере одно из следующих условий для E( i 1 , i 2 , j 1 , j 2 ):

  1. E( i 1 , i 2 , j 1 , j 2 ) содержит не более одного элемента;
  2. Объединение горизонтальных отрезков ( x i , x i + w i ) по всем i в E( i 1 , i 2 , j 1 , j 2 ) состоит по крайней мере из двух непересекающихся интервалов;
  3. Объединение вертикальных отрезков ( y i , y i + h i ) по всем i из E( i 1 , i 2 , j 1 , j 2 ) состоит по крайней мере из двух непересекающихся интервалов.

Условие 2 подразумевает, что прямоугольники в E( i 1 , i 2 , j 1 , j 2 ) могут быть разделены вертикальным разрезом (проходящим между двумя непересекающимися горизонтальными интервалами); условие 3 подразумевает, что прямоугольники в E( i 1 , i 2 , j 1 , j 2 ) могут быть разделены горизонтальным разрезом. Все условия вместе подразумевают, что если любой набор смежных прямоугольников содержит более одного элемента, то их можно разделить некоторым гильотинным разрезом.

Проверить это условие можно по следующему алгоритму.

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

Поиск гильотинного реза для заданного шаблона выполняется следующим образом:

  • Определите m горизонтальных интервалов и упорядочите их слева направо; определите m вертикальных интервалов и упорядочите их снизу вверх. Это займет O( m log m ) времени.
  • Объединить перекрывающиеся горизонтальные интервалы и объединить перекрывающиеся вертикальные интервалы. Это занимает O( m ) времени.
  • Если после слияния имеется по крайней мере два непересекающихся горизонтальных интервала, то возможен вертикальный гильотинный разрез; если имеется по крайней мере два непересекающихся вертикальных интервала, то возможен горизонтальный разрез; в противном случае разрез невозможен.

Шаг упорядочения выполняется один раз, а шаг слияния выполняется m -1 раз. Таким образом, время выполнения всего алгоритма составляет O( m 2 ).

Когда алгоритм возвращает «да», он также создает последовательность разрезов гильотиной; когда он возвращает «нет», он также создает определенные подмножества прямоугольников, которые невозможно разделить разрезами гильотиной.

Необходимое и достаточное условие можно использовать для представления задачи разрезания гильотиной полосы как смешанной целочисленной линейной программы . [5] : раздел 5  Их модель имеет 3 n 4 /4 двоичных переменных и 2 n 4 ограничений и считается бесполезной на практике.

Нахождение оптимальной схемы раскроя

Это варианты задач двумерной резки материала , упаковки в контейнеры и упаковки прямоугольников , где разрезы ограничены разрезами гильотины. [6]

  • В базовой ( невзвешенной ) задаче гильотинной резки требуемым результатом является последовательность гильотинных разрезов, в результате которых получаются куски заданных размеров, при этом общая площадь полученных кусков максимальна (что эквивалентно минимизации отходов от необработанного прямоугольника).
  • В взвешенном варианте для каждого целевого измерения i также есть значение v i . Цель состоит в том, чтобы максимизировать общую стоимость произведенных деталей. Невзвешенный (минимизация отходов) вариант может быть сведен к взвешенному варианту, если значение каждого целевого измерения будет равно его площади ( v i = h i * w i ).
  • В ограниченном варианте для каждого целевого измерения i существует верхняя граница b i количества деталей этого типа, которые могут быть произведены.
    • В варианте с двойными ограничениями для каждого целевого измерения i существует как нижняя граница a i , так и верхняя граница b i количества произведенных изделий.
  • Двоичный вариант — это ограниченный вариант, в котором каждое целевое измерение должно появляться не более одного раза (т. е. верхняя граница равна 1). Этот случай связан с проблемой принятия решения , где цель состоит в том, чтобы решить, возможно ли создать один элемент каждого целевого измерения с помощью гильотинных разрезов. [4]
  • В задаче о гильотинной резке полос большой прямоугольник имеет бесконечную высоту (но фиксированную ширину), и цель состоит в том, чтобы вырезать один прямоугольник каждого типа, так чтобы общий используемый материал (эквивалентно общей высоте) был минимизирован. Это вариант двумерной задачи упаковки полос .
  • В задаче минимизации запаса имеется бесконечное количество листов запаса одинаковых размеров, и цель состоит в том, чтобы вырезать все требуемые целевые прямоугольники, используя наименьшее возможное количество листов. [5] Это вариант двумерной задачи упаковки в контейнеры . [7]
  • k-ступенчатая гильотинная резка — это ограниченный вариант гильотинной резки, при котором резка выполняется не более чем за k этапов: на первом этапе выполняются только горизонтальные разрезы; на втором этапе выполняются только вертикальные разрезы и т. д.
    • В двухэтапном варианте еще одно различие заключается в том, разрезаются ли все полосы, полученные в результате первого этапа, в одних и тех же местах (называется «1-группа») или в двух разных местах (называется «2-группа»), или в возможно разных местах (называется «свободный»). [8]
  • 1-Простая гильотинная резка — это ограниченный вариант гильотинной резки, при котором каждый разрез разделяет один прямоугольник.
    • 2 -простая гильотинная резка — это 1-простая схема, каждая часть которой сама является 1-простой. p -простые схемы резки могут быть определены рекурсивно. [9]

Алгоритмы оптимизации

Частный случай, в котором существует только один тип (т. е. все целевые прямоугольники идентичны и имеют одинаковую ориентацию), называется задачей загрузки паллет гильотиной . Тарновски, Терно и Шайтхауэр [10] представляют полиномиальный алгоритм для ее решения.

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

  • Гилмор и Гомори [11] [12] представили динамическую рекурсию программирования как для поэтапной, так и для неэтапной резки гильотиной. Однако позже было показано [13] [2] , что оба алгоритма содержали ошибки. Бисли [2] представил правильный алгоритм динамического программирования.
  • Герц [13] , Кристофидес и Уитлок [14] представили процедуры поиска по дереву для неступенчатой ​​гильотинной резки.
  • Масден [15] и Ван [16] представили эвристические алгоритмы .
  • Хиффи, М'Халлах и Саади [6] предлагают алгоритм для задачи гильотины с двойным ограничением. Это алгоритм ветвей и границ снизу вверх, использующий поиск по лучшему первому .
  • Клотио, Жугле и Мукрим [4] предлагают точный алгоритм для задачи решения. Их алгоритм использует компактное представление классов шаблонов разрезания гильотины, используя направленный граф , который они называют графом гильотины . Каждая дуга в этом графе окрашена в один из двух цветов: «горизонтальный» или «вертикальный». Каждый одноцветный направленный цикл в этом графе соответствует построению. Многократно сокращая одноцветные циклы, можно восстановить рекурсивную последовательность построения, которая представляет класс шаблонов разрезания. Каждый граф гильотины содержит от m до 2 m -2 дуг. Особый вид графов гильотины, называемый нормальными графами гильотины, обладает интересным свойством содержать уникальный гамильтонов контур . Сортировка вершин в соответствии с этим контуром делает граф хорошо отсортированным нормальным графом гильотины ; между такими графами и классами шаблонов разрезания существует взаимно-однозначное соответствие. Затем они решают задачу оптимизации, используя программирование ограничений на пространстве хорошо отсортированных нормальных гильотинных графов.
  • Руссо, Бочча, Сфорца и Стерле [8] рассматривают более 90 статей, посвященных неустановленному ограниченному гильотинному разрезанию (с верхними границами количества), как взвешенному, так и невзвешенному. Существует два основных подхода к точным решениям: динамическое программирование и поиск по дереву (ветви и границы). Подходы поиска по дереву далее подразделяются на восходящие (начинающиеся с отдельных прямоугольников и использующие построения для построения всего листа) или нисходящие . Во всех подходах важно найти хорошие нижние и верхние границы, чтобы эффективно урезать пространство поиска. Эти границы часто берутся из решений для связанных вариантов, например, неустановленных, поэтапных и негильотинных вариантов.
  • Абу Мсабах, Слиман и Ахмед Риад Баба-Али. «Новая эвристика размещения гильотины в сочетании с улучшенным генетическим алгоритмом для задачи ортогонального раскроя». Международная конференция IEEE по промышленной инженерии и инженерному менеджменту 2011 г. IEEE, 2011.
  • Абу-Мсабах, Слиман, Ахмед-Риад Баба-Али и Басма Сагер. «Генетический алгоритм контролируемой устойчивости с новой эвристикой размещения гильотины BLF2G для задачи ортогональной резки». Международный журнал когнитивной информатики и естественного интеллекта (IJCINI) 13, № 4 (2019): 91–111.

Реализации

  • Макхейл и Шах [17] написали программу Prolog, реализующую алгоритм anytime : она генерирует приблизительно оптимальные решения за заданное время, а затем улучшает их, если пользователь дает больше времени. Программа использовалась производителем специальной бумаги и сократила время, необходимое для макета листа, одновременно уменьшив отходы.

Гильотинное разделение

Разделение гильотиной — это связанная задача, в которой входными данными является набор n попарно непересекающихся выпуклых объектов на плоскости, а целью является их разделение с помощью последовательности разрезов гильотиной. Очевидно, что разделить их все может быть невозможно. Хорхе Уррутия Галисия спросил [18], возможно ли разделить постоянную часть из них, то есть существует ли константа c такая, что в любом таком наборе размера n существует подмножество размера cn, которое можно разделить с помощью гильотины.

Пах и Тардос [19] доказали:

  • Если все объекты имеют одинаковый размер, то постоянная их доля может быть разделена. Формально, если все объекты содержат круг радиуса r и содержатся в круге радиуса R , то существует разделяемое множество размера . Доказательство : постройте сетку с размером ячейки 8 R на 8 R. Перемещайте сетку равномерно случайным образом. Каждый объект пересекается горизонтальной линией с вероятностью 1/4 и вертикальной линией с вероятностью 1/4 тоже, поэтому ожидаемое количество пересеченных объектов равно . Следовательно, существуют линии сетки, которые пересекаются в большинстве объектов. Поскольку площадь каждой ячейки сетки равна и площадь каждого объекта равна не менее , каждая ячейка содержит не более объектов. Выберите один объект из каждой ячейки и отделите его от других объектов в той же ячейке. Общее количество объектов, разделенных таким образом, равно не менее Аналогичное рассуждение для случая единичных квадратов дает π г 2 128 Р 2 н ≈ 1 40.7 ( Р / г ) 2 н {\displaystyle {\frac {\pi r^{2}}{128R^{2}}}n\approx {\frac {1}{40,7(R/r)^{2}}}n} н / 2 {\displaystyle n/2} н / 2 {\displaystyle n/2} ( 8 Р ) 2 {\displaystyle (8R)^{2}} π г 2 {\displaystyle \пи г^{2}} ( 8 Р ) 2 π г 2 {\displaystyle {\frac {(8R)^{2}}{\pi r^{2}}}} н 2 / ( 8 Р ) 2 π г 2 = π г 2 128 Р 2 н . {\displaystyle {\frac {n}{2}}/{\frac {(8R)^{2}}{\pi r^{2}}}={\frac {\pi r^{2}}{128R^{2}}}n.} 1 27 n . {\displaystyle {\frac {1}{27}}n.}
  • Если объекты являются прямыми отрезками, то в некоторых случаях только в большинстве из них можно разделить. В частности, для каждого положительного целого числа k существует семейство непересекающихся интервалов, такое, что в большинстве из них можно разделить. O ( n log 3 ⁡ 2 ) ≈ O ( n 0.63 ) {\displaystyle O(n^{\log _{3}{2}})\approx O(n^{0.63})} 3 k {\displaystyle 3^{k}} 2 k {\displaystyle 2^{k}}
  • В любой совокупности из n выпуклых объектов по крайней мере можно разделить. Ω ( n 1 / 3 ) {\displaystyle \Omega (n^{1/3})}
  • В любой коллекции из n прямых отрезков, по крайней мере, можно разделить. Они предполагают, что худший случай может быть достигнут с помощью прямых отрезков. Ω ( n 1 / 2 ) {\displaystyle \Omega (n^{1/2})}
  • В любой коллекции из n прямоугольников, параллельных осям, по крайней мере, можно разделить. Они предполагают, что можно разделить; эта гипотеза все еще открыта. n / ( 2 log ⁡ n ) {\displaystyle n/(2\log {n})} Ω ( n ) {\displaystyle \Omega (n)}
  • В любой коллекции объектов размером R ( наименьший содержащий диск не превышает R раз большего содержащегося диска) можно сохранить не менее объектов, где — константа, зависящая только от R. n / ( c R log ⁡ n ) {\displaystyle n/(c_{R}\log {n})} c R {\displaystyle c_{R}}
    • Аналогичная теорема справедлива и в более высоких измерениях: число разделяемых объектов равно . n / c ( R , d ) ( log ⁡ n ) d {\displaystyle n/c(R,d)(\log {n})^{d}}
  • Все эти разделимые подсемейства могут быть построены за время . Если объекты являются многоугольниками с N сторонами в целом, то разделительные линии могут быть вычислены за время . O ( n log ⁡ n ) {\displaystyle O(n\log {n})} O ( N + n log ⁡ n ) {\displaystyle O(N+n\log {n})}

Абед, Чалермсук, Корреа, Карренбауэр, Перес-Лантеро, Сото и Визе [20] доказали:

  • В любой совокупности из n единичных квадратов, параллельных осям, можно разделить не менее n /2, а существуют случаи, когда можно разделить не более n /2.
  • В любой совокупности из n квадратов, параллельных осям, можно выделить по крайней мере n /81.
  • В любой совокупности из n квадратов с параллельными осями и грузами можно разделить не менее 4/729 от общего веса.
  • В любой коллекции из n параллельных осям d -мерных кубов с грузами можно выделить часть общего веса. 1 / 2 O ( d ) {\displaystyle 1/2^{O(d)}}
  • Что касается гипотезы о возможности разделения прямоугольника, параллельного осям, то, хотя они ее и не опровергают, они показывают, что если она верна, то она подразумевает алгоритм приближения O(1) к задаче о максимальном непересекающемся наборе прямоугольников, параллельных осям, за время . Ω ( n ) {\displaystyle \Omega (n)} O ( n 5 ) {\displaystyle O(n^{5})}

Хан и Питту [21] доказали:

  • Если в случае n прямоугольников с параллельными осями допускаются только этапы, то разделить прямоугольники невозможно . o ( log ⁡ log ⁡ n ) {\displaystyle o(\log \log n)} Ω ( n ) {\displaystyle \Omega (n)}
  • Если при взвешивании прямоугольников допускаются только этапы, то разделить вес невозможно . o ( log ⁡ n / log ⁡ log ⁡ n ) {\displaystyle o(\log {n}/\log \log {n})} Ω ( n ) {\displaystyle \Omega (n)}
  • Существует простой двухэтапный алгоритм, который разделяет прямоугольники. Алгоритм разбивает прямоугольники на подмножества (называемые «уровнями») и выбирает уровень с наибольшим количеством прямоугольников. Каждый уровень может быть разделен двумя гильотинными разрезами. [21] : Теория 14  Улучшенный алгоритм может разделять прямоугольники. n / ( 1 + log 2 ⁡ n ) {\displaystyle n/(1+\log _{2}{n})} 1 + log 2 ⁡ n {\displaystyle 1+\log _{2}{n}} n / log 3 ⁡ ( n + 2 ) {\displaystyle n/\log _{3}{(n+2)}}
  • В любой коллекции толстых прямоугольников , их можно разделить. Ω ( n ) {\displaystyle \Omega (n)}
  • В любой совокупности из n квадратов, параллельных осям, можно выделить не менее n /40.
  • В любой совокупности из n квадратов с параллельными осями и грузами можно отделить по крайней мере часть, составляющую 1/80 от общего веса.

Смотрите также:

Больше вариантов

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

  • Гильотинная резка в трех измерениях. [22] [23]
  • Гильотинная резка, когда необработанный прямоугольник может иметь дефекты, но полученные прямоугольники должны быть бездефектными. [24]

Ссылки

  1. ^ Tlilane, Lydia; Viaud, Quentin (2018-05-18). "Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description" (PDF) . Challenge ROADEF/EURO . ROADEF . Получено 2019-06-13 .
  2. ^ abcd Бисли, Дж. Э. (1985-04-01). «Алгоритмы для неограниченной двумерной гильотинной резки». Журнал Общества исследований операций . 36 (4): 297– 306. doi :10.1057/jors.1985.51. ISSN  0160-5682. S2CID  58059319.
  3. ^ Герхард Вешер, Хайке Хауснер, Хольгер Шуман, Улучшенная типология задач резки и упаковки, Европейский журнал операционных исследований 183 (2007) 1109–1130, [1] Архивировано 20 декабря 2016 г. на Wayback Machine
  4. ^ abc Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (2011-10-17). «Новая теоретико-графовая модель для задачи гильотинного раскроя». INFORMS Journal on Computing . 25 (1): 72– 86. doi :10.1287/ijoc.1110.0478. ISSN  1091-9856.
  5. ^ abc Бен Мессауд, Саид; Чу, Ченгбин; Эспинуз, Мари-Лор (2008-11-16). «Характеристика и моделирование ограничений гильотины». Европейский журнал операционных исследований . 191 (1): 112– 126. doi :10.1016/j.ejor.2007.08.029. ISSN  0377-2217.
  6. ^ ab M. Hifi, R. M'Hallah и T. Saadi, Приближенные и точные алгоритмы для двумерной задачи гильотинной резки с двойными ограничениями. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi :10.1007/s10589-007-9081-5
  7. ^ Карлье, Жак; Клотио, Франсуа; Мукрим, Азиз (2007-08-01). «Новые процедуры редукции и нижние границы для двумерной задачи упаковки контейнеров с фиксированной ориентацией». Computers & Operations Research . 34 (8): 2223– 2250. doi :10.1016/j.cor.2005.08.012. ISSN  0305-0548.
  8. ^ ab Руссо, Мауро; Бочча, Маурицио; Сфорца, Антонио; Стерле, Клаудио (2020). «Ограниченная двумерная задача резки гильотиной: обзор верхней границы и категоризация». Международные труды по исследованию операций . 27 (2): 794– 834. doi : 10.1111/itor.12687. ISSN  1475-3995. S2CID  195551953.
  9. ^ Шейтхауэр, Гунтрам (1993). "Вычисление оптимальных φ-простых схем гильотинной резки" (PDF) . Журнал обработки информации и кибернетики . 29 (2): 115–128 .
  10. ^ Tarnowski, AG; Terno, J.; Scheithauer, G. (1 ноября 1994 г.). «Алгоритм полиномиального времени для задачи загрузки поддонов гильотиной». INFOR: Информационные системы и операционные исследования . 32 (4): 275– 287. doi :10.1080/03155986.1994.11732257. ISSN  0315-5986.
  11. ^ Гилмор, ПК; Гомори, Р. Э. (1965-02-01). «Задачи многоэтапной резки заготовки двух и более измерений». Исследование операций . 13 (1): 94– 120. doi :10.1287/opre.13.1.94. ISSN  0030-364X.
  12. ^ Гилмор, ПК; Гомори, Р. Э. (1966-12-01). «Теория и вычисление функций ранца». Исследование операций . 14 (6): 1045– 1074. doi :10.1287/opre.14.6.1045. ISSN  0030-364X.
  13. ^ ab Herz, JC (сентябрь 1972 г.). «Рекурсивная вычислительная процедура для двумерной резки запаса». IBM Journal of Research and Development . 16 (5): 462– 469. doi :10.1147/rd.165.0462. ISSN  0018-8646.
  14. ^ Кристофидес, Никос; Уитлок, Чарльз (1977-02-01). «Алгоритм для задач двумерного раскроя». Исследование операций . 25 (1): 30–44 . doi :10.1287/opre.25.1.30. ISSN  0030-364X.
  15. ^ OBG Masden (1980), рабочий документ IMSOR, Технический университет Дании, Люнгбю
  16. ^ Ван, PY (1 июня 1983 г.). «Два алгоритма для задач двумерного раскроя с ограничениями». Исследование операций . 31 (3): 573– 586. doi :10.1287/opre.31.3.573. ISSN  0030-364X.
  17. ^ Майкл Л. Макхейл, Рошан П. Шах. Сокращение гильотины до нужного размера. Журнал PC AI, том 13, номер 1, янв./февр. 99. http://www.amzi.com/articles/papercutter.htm
  18. ^ Задача, представленная на ACCOTA '96, Комбинаторные и вычислительные аспекты оптимизационной топологии и алгебры, Таско, Мексика, 1996 г.
  19. ^ Pach, J.; Tardos, G. (2000). «Резание стекла». Дискретная и вычислительная геометрия . 24 ( 2– 3): 481– 496. doi : 10.1007/s004540010050 . ISSN  0179-5376. S2CID  1737527.
  20. ^ Абед, Фидаа; Чалермсук, Паринья; Корреа, Хосе; Карренбауэр, Андреас; Перес-Лантеро, Пабло; Сото, Хосе А.; Визе, Андреас (2015). О последовательности гильотинной резки. стр.  1–19 . doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7.
  21. ^ ab Khan, Arindam; Pittu, Madhusudhan Reddy (2020). Byrka, Jaros\law; Meka, Raghu (ред.). "On Guillotine Separability of Squares and Rectangles". Approximation, Randomization, and Combinatory Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) . Leibniz International Proceedings in Informatics (LIPIcs). 176. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 47:1–47:22. doi : 10.4230/LIPIcs.APPROX/RANDOM.2020.47 . ISBN 978-3-95977-164-1.
  22. ^ Мартин, Матеус; Оливейра, Хосе Фернандо; Сильва, Эльза; Морабито, Рейнальдо; Мунари, Педро (08.11.2020). «Задачи трехмерной гильотинной резки с ограниченными шаблонами: формулировки MILP и восходящий алгоритм». Экспертные системы с приложениями . 168 : 114257. doi : 10.1016/j.eswa.2020.114257. ISSN  0957-4174. S2CID  228839108.
  23. ^ Baazaoui, M.; Hanafi, S.; Kamoun, H. (2014-11-01). "Математическая формулировка и нижняя граница для трехмерной задачи упаковки контейнеров нескольких размеров (MBSBPP): Тунисский промышленный случай". 2014 Международная конференция по технологиям управления, принятия решений и информации (CoDIT) . стр.  219–224 . doi :10.1109/CoDIT.2014.6996896. ISBN 978-1-4799-6773-5. S2CID  18598442.
  24. ^ Мартин, Матеус; Хокама, Педро HDB; Морабито, Рейнальдо; Мунари, Педро (2020-05-02). «Ограниченная двумерная задача резки гильотиной с дефектами: формулировка ILP, разложение Бендерса и алгоритм на основе CP». Международный журнал исследований производства . 58 (9): 2712– 2729. doi :10.1080/00207543.2019.1630773. ISSN  0020-7543. S2CID  197434029.

Абу Мсабах, Слиман и Ахмед Риад Баба-Али. «Новая эвристика размещения гильотины в сочетании с улучшенным генетическим алгоритмом для задачи ортогонального раскроя». Международная конференция IEEE по промышленной инженерии и инженерному менеджменту 2011 г. IEEE, 2011.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Guillotine_cutting&oldid=1241541917#separation"