作业调度探测的变化

Question

我在为一家航空运输公司做一些行政工作。他们在这里建造飞机集装箱之类的东西。他们希望我编写的其中一件事是一个订单优化脚本，地板上的人可以使用它来最大限度地利用给定的材料。给出一个简单的概述:假设我们订购了一定数量的光束，每单位10米。我们需要5x6m，10x3.5m，4x3m的梁块，它们是通过将10米分成更小的部分来获得的。我们需要订购的10m波束的最低数量是多少？

与多处理器作业调度问题(一个波束是一个处理器，每个块是一个作业)有一些相似之处，尽管它专注于最小化执行所有作业所需的时间，而不是最小化在预设时间内执行所有作业所需的处理器数量。多处理器作业调度问题是NP完全的，但我想知道我的问题变体是否也是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/，它使用起来很友好。