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

StackOverflow https://stackoverflow.com/questions/1405837

Вопрос

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

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

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

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

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

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

У вас есть какие-нибудь подсказки?

Это было полезно?

Решение

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

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

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

Другие советы

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

Линейное программирование - твой друг. См. http://en.wikipedia.org/wiki/Linear_programming в целом и, в частности, , http://en.wikipedia.org/wiki/Linear_programming#Uses , < a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top