Каков эффективный алгоритм для вложения одномерных длин в предварительно определенные длины заготовки?
Например, если вам потребовались стальные прутки в следующих количествах и длинах,
- 5 х 2 метра
- 5 х 3 метра
- 5 х 4 метра
и они могут быть вырезаны из 10 метровых баров.
Как вы можете рассчитать схему резки 10-метровых прутков, чтобы использовать минимальное количество прутков?
Кроме того, как вы могли бы включить в алгоритм несколько длин заготовок?
У меня было немного времени, чтобы поработать над этим, поэтому я собираюсь написать, как я это решил. Я надеюсь, что это будет кому-то полезно. Я не уверен, что можно ответить на мой собственный вопрос, как этот. Модератор может изменить это на ответ, если это более уместно.
Во-первых, спасибо всем, кто ответил. Это указало мне на соответствующий алгоритм; проблема режущего материала .
Этот пост был также полезен; «Расчет списка вырезов с наименьшим количеством отходов» .
Хорошо, перейдем к решению.
Я буду использовать следующую терминологию в своем решении;
- Запас: длина материала, который будет разрезан на более мелкие кусочки
- Вырезать: отрезанный материал со склада. из одного и того же запаса можно сделать несколько надрезов
- Отходы: длина материала, который остается в заготовке после того, как все надрезы были сделаны.
Существует три основных этапа решения проблемы,
- Укажите все возможные комбинации разрезов
- Укажите, какие комбинации можно взять с каждого куска запаса.
- Найдите оптимальное сочетание комбинаций разрезов.
Шаг 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.
Добавить 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% для некоторых типичных данных испытаний. Надеюсь, я когда-нибудь вернусь к этой проблеме и попробую реализовать алгоритм Delayed column генерация . Это должно дать лучшие результаты.
Надеюсь, это помогло кому-нибудь еще, столкнувшемуся с этой проблемой.
David