計算最佳庫存長度

Question

這與cutting stock problem類似，但略有差異。我想知道什麼樣的股票的最佳長度是基於裁剪的大小。

潛在的併發症：

1. 上料問題維基百科的文章是在我頭上的方式。我懷疑如何解決這個問題對解決我自己的問題至關重要。

2. 一些切割長度比其他切割長度更常見。小於2英尺的任何東西都被認爲是廢料，所以我們寧願不剪切留下大塊廢料。另一方面，我們不想掛在衆多的部分股票上，希望有一天我們可能需要其中一個。

Answer 1

我是否正確理解這一點：您有不同的切割長度（3.6,10.2,8.3， 7.3，...） 你想知道什麼stocklength是最好的給你最少的切割浪費？你想找到一個stocklength，或多個？有最大長度，最小長度嗎？如果你沒有最大長度，最好的選擇是使用一個非常長的股票，所有的切割長度完全吻合，但我不認爲這是你想要的。

UPDATE我一直在努力作爲我工作的一部分，這個問題有一段時間，我們有一個產品可以做到這一點（還有更多）。對於一個簡單的解決方案，您可以實現一個First Fit Decreasing啓發式，可以與給定的庫存長度一起工作。然後隨機使用幾種股票的長度，每次使用啓發式來填補它們。記住股票的最小浪費。

如果你想要一個更先進的算法，我勸你買我們的軟件:-)

Answer 2

問題還取決於您想要使用的股票數量。

如果S = 1，那麼庫存長度應該是所有切割尺寸的總和。

如果S> 1，那麼您希望將切割的大小劃分爲S個組，並且最小化每個組中切割大小總和之間的差異。這非常接近partition problem，這是NP難度。

Answer 3

看來你有這個「在線」版本或類似的優化問題。 在線意味着您不提前知道所有信息，即 即您必須根據訂單進行決策。