Алгоритм установки досок на имеющиеся длины, сводя к минимуму отходы

Question

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

3x 2,9 метра
5x 1,6 метров
21х 0,9 м

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

Простой подход был бы попробовать и подходят остальные платы в нисходящей длине:

2,9 + 2,9 = 5,8, так что не будет соответствовать на борте 4,8 метра
2,9 + 1,6 = 4,5 так ничего страшного.

Никакой длины меньше, чем остальные 0,3 метра, поэтому эта доска является «полной». Мы поместится больше этого типа два, а затем мы следующие длины влево, чтобы соответствовать:

2x 1,6 метра
21х 0,9 м

Ok, так что этот алгоритм работает достаточно хорошо. Но что, если мы вместо того, чтобы подгонять 2,9 + 1,6, вместо этого заменим 2.9 + 0.9 + 0.9 = 4.7. Затем мы получим 0,1 м отходов на борту, вместо 0,3 метра.

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

Кроме того, что, если на дворе древесины есть две или более длины? Например, 5,4, 4,8 и 3,6 метра? Это, безусловно, усложнит ситуацию. Можно выполнить выбранный алгоритм для каждой доступной длины и выбрать длину с наименьшим количеством отходов. Но самое элегантное решение позволило бы смешивать имеющиеся длины, поэтому оптимальный ответ мог бы быть чем-то вроде 1x 5.4, 3x 4.8, 6x 3.6. Но для начала я был бы доволен ограничением ответа на одну длину.

Answer 1

@Anlo,

Ваша конкретная проблема является вариант так называемого «Cutting Stock» класса задач. Взгляните на страницу «Cutting Stock Problem» (CSP) Википедии

Мне нравится это объяснение на простом английском языке более простой версии проблемы резки. От AIMMS:

«задача раскроя: как сократить длинные рулоны материала (называемый , как бараны) на меньшие рулоны заданного размера (далее как финал), учитывая спрос на каждый из в финале ».

Обратите внимание, что существует немало изменений в проблеме основной резки, которую исследователи придумали. В этих лекциях по программированию целых чисел хорошая формулировка generalized Cutting Stock problem (см. Стр. 17)

Эти проблемы с MILP нелегко сформулировать, поскольку целевая функция и ограничения соответствуют основному образцу стандартного CSP. Существует огромное количество исследований по методам их эффективного решения.

Если у вас есть доступ к решателю LP/IP, например CPLEX, R или Excel Solver (для небольших проблем), определенно стоит сформулировать вашу проблему и попробовать ее на этих решателях.

Надеюсь, что это поможет.

Answer 2

Минимизации отходов на самом деле проблема оптимизации для обобщенных subset sum problem, что NP-Complete, и, таким образом, нет никакого известного полиномиального решения времени для решения этой проблемы

Хотя NP-полный, можно производить pseudo-polynomial solution для этой задачи с использованием динамического программирования или уменьшения его до knapsack (вес = значение = длина, W = размер платы) и используйте его pseudo-polynomial solution, что очень похоже.

Однако здесь это еще сложнее, псевдополиномиальное решение принимает целые числа, в то время как ваши примеры показывают, что это не так. Вы можете решить это, используя fixed point arithmetics для представления длин (т.е. 4.8 будет отображаться как 48, если вы используете только одну цифру после точки на длину, если вы используете 2 цифры после точки, это будет 480, .. .).

Примечание: этот алгоритм минимизирует отходы для вас, но это не гарантирует «минимальное количество журналов» для минимизированных отходов.

В любом случае, поскольку поиск любого решения является NP-Hard, поиск решения, использующего наименьшие журналы, также NP-Hard.