Проблема промышленного разделения

Question

Речь идет о заводе металлопродукции. Есть машина, которая разрезает длинные железные прутки на более мелкие детали, которые впоследствии используются для создания различных продуктов.

Например, у меня есть требование производить бары следующей длины и количества: 2 шт. 248 мм, 5 из 1150мм, 6 из 2843 мм, 3 из 3621мм.

Это вывод разделов.

На входной стороне у меня есть (опять например) 3 бара по 2500мм, 2 бара по 5000мм, 6 прутков 8000 мм и 3 бара по 10000мм.

Я должен найти способ оптимальной резки входных стержней - остальные (оставшиеся детали, которые слишком малы для использования) после резки должны быть как можно меньше.

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

У вас есть какие-нибудь намеки?

Answer 1

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

Как это решить? После того, как вы сможете выяснить модель, было бы лучше назвать какой-нибудь смешанный целочисленный программный решатель. Я ранее использовал LPSolve 5.5

Там могут быть более простые алгоритмы, которые вы могли бы кодировать, в частности, для решения этой проблемы. Проблема с этими алгоритмами обычно возникает, когда вам нужно добавить некоторые побочные ограничения, о которых авторы не думали. MIP Solver - более универсальный инструмент.

Answer 2

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

Answer 3

Похоже, что это похоже на проблему с рюкзаком (знаю, что это действительно противно). Я нашел это на NIST DADS (удобный справочник) проще, чем ACM для не членов Bin Packing

Answer 4

Линейное программирование - твой друг. См. http://en.wikipedia.org/wiki/Linear_programming в целом и, в частности, http://en.wikipedia.org/wiki/Linear_programming#Uses, http://en.wikipedia.org/wiki/Linear_programming#Algorithms.