Резка труб определенной длины (бункерная упаковка с постоянным количеством типов изделий) - PullRequest
0 голосов
/ 02 апреля 2019

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

1 Ответ

0 голосов
/ 07 апреля 2019

Как отметил Кодор, это проблема с упаковкой бункера. По крайней мере, это подкласс: существует еще одна категория, называемая проблемой «Режущий материал», где «вес» материала классифицируется в виде нескольких отдельных категорий и не является непрерывным значением.

Проблема упаковки бункера - это проблема NP, которая означает, что оптимальное решение может быть найдено путем опробования всех возможных решений. Что касается режущего материала: он более ограничен и есть алгоритмы полиномиального решения, открытые Томасом Ротвоссом (или Ротвоссом). Я еще не понял этого, но если кому-то интересно, есть статья «Полиномиальность для упаковки бина с постоянным количеством типов предметов» и видео на Youtube Лучшие алгоритмы для упаковки бина . К сожалению, я пока не нашел исходный код, реализующий алгоритмы.

...