工作調度問題的變化

Question

我正在爲航空運輸公司做一些管理工作。他們在這裏建造飛機容器等。他們希望我編寫代碼的一件事就是一個訂單優化腳本，這些腳本可以讓場內人員充分利用所提供的材料。爲了給出一個簡單的概述：假設我們訂購一定數量的單位爲10米的光束。我們需要5x6m，10x3.5m，4x3m的波束塊，這些波塊通過在較小的部分切割10m而獲得。我們需要訂購的最小數量爲10m的光束是多少？

有一些相似之處上述多任務調度問題（一個束是處理器，每個組塊的作業），雖然這對最小化來執行的所有作業所需要的時間，而不是最小化來執行所有所需的處理器的量論點集中在預先設定的時間內工作。多處理器作業調度問題是NP完全的，但我不知道我的問題的變化是否也是如此。有人知道解決它們的類似問題和方法嗎？

Answer 1

這個問題正是：http://en.wikipedia.org/wiki/Cutting_stock_problem（更一般地說是http://en.wikipedia.org/wiki/Bin_packing_problem）。您可以使用任何舊的ILP解算器。我喜歡http://lpsolve.sourceforge.net/5.5/，它的使用相當友好。