1-мерный алгоритм вложения

Каков эффективный алгоритм вложения одномерных длин в заранее определенные длины заготовки?

Например, если вам требуются стальные стержни в следующих количествах и длинах,

• 5 х 2 метра
• 5 х 3 метра
• 5 х 4 метра

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

Кроме того, как можно включить в алгоритм несколько длин акций?

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

Во первых спасибо всем ответившим. Это указало мне на соответствующий алгоритм; проблема раскроя.

Этот пост также был полезен; "Расчет списка резки с наименьшим количество обрезков".

Хорошо, к решению.

В своем решении я буду использовать следующую терминологию;

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

Выделяют три основных этапа решения проблемы,

1. Определите все возможные комбинации вырезов
2. Определите, какие комбинации могут быть взяты из каждой части запаса
3. Найдите оптимальное сочетание комбинаций огранки.

Шаг 1

С N разрезами существует 2 ^ N-1 уникальных комбинаций разрезов. Эти комбинации могут быть представлены в виде бинарной таблицы истинности.

Где A,B,C — уникальные разрезы;

A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC

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

Это может занять довольно много времени для больших значений N.

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

A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB

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

Например, с разрезами AABBC процесс выглядит следующим образом.

A A | Combination
-------------------
0 1 | A 
1 1 | AA

Назовите эту группу Х.

Добавить X к уникальным экземплярам B,

B B X | Combination
-------------------
0 0 1 | A 
      | AA
0 1 0 | B
0 1 1 | BA
      | BAA
1 1 0 | BB 
1 1 1 | BBA
      | BBAA

Назовите эту группу Y.

Добавить Y к уникальным экземплярам C,

C Y | Combination
-----------------
0 1 | A 
    | AA
    | B
    | BA
    | BAA
    | BB 
    | BBA
    | BBAA 
1 0 | C
1 1 | CA 
    | CAA
    | CB
    | CBA
    | CBAA
    | CBB 
    | CBBA
    | CBBAA 

В этом примере получается 17 уникальных комбинаций вместо 31 (2^5-1). Экономия почти половина.

Как только все комбинации определены, пришло время проверить, как они вписываются в акции.

Шаг 2

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

Это относительно простой процесс. Для каждой комбинации разрезов

   calculate the sum of all cut lengths.
   for each item of stock, 
        if the sum of cuts is less than stock length,
            store  stock, cut combination and waste in a data structure.
            Add this structure to a list of some sort.

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

Шаг 3

На этом шаге мы определим комбинацию разрезов, которая производит наименьшие отходы. Это основано на списке допустимых раскладок, сгенерированном на шаге 2.

В идеальном мире мы бы просчитали все возможности и выбрали наилучшую. Для любого нетривиального набора разрезов потребуется вечность, чтобы вычислить их все. Нам остается довольствоваться неоптимальным решением. Существуют различные алгоритмы выполнения этой задачи.

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

Начните с трех списков

• cutList: список всех необходимых разрезов (включая дубликаты).
• NestList: список гнезд, созданный на шаге 2. Он отсортирован от наименьшего количества отходов до самого высокого количества отходов.
• finalList: изначально пустой, в нем будет храниться список комбинаций вырезов, которые будут выведены пользователю.

Метод

pick nest from nestList with the least waste
  if EVERY cut in the nest is contained in cutList
     remove cuts from cutList
     copy this nest into the finalList
  if some cuts in nest not in cutList
      remove this nest from nestList             
repeat until cutlist is empty

С помощью этого метода мне удалось получить около 2-4% потерь для некоторых типичных тестовых данных. Надеюсь, что когда-нибудь я вернусь к этой проблеме и попытаюсь реализовать отложенное создание столбцов алгоритм. Это должно дать лучшие результаты.

Я надеюсь, что это помогло кому-то еще с этой проблемой.

Дэйвид