二维板材切割下料问题的一种确定性算法

研究二维板材切割下料问题，即使用最少板材切割出一定数量的若干种矩形件。 提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方 式的背包算法；然后采用线性规划算法迭代调用上述背包算法，每次均根据生产成本最小原则 改善目标函数并修正各种矩形件的当前价值，按照当前价值生成新的排样方式；最后选择最优 的一组排样方式组成排样方案。采用基准测题，将该算法与著名的T 型下料算法进行比较，实 验结果表明，该算法比T 型下料算法更能节省板材，计算时间能够满足实际应用需要。

A Deterministic Algorithm for Solving the Problem of#br# Two-Dimensional Sheet Cutting Stock

This paper discusses the two dimensional sheet cutting stock problem, that is, use the least number of sheets to cut out a certain number of rectangular pieces. A deterministic algorithm is proposed which based on the combination of knapsack algorithm and linear programming algorithm. First, a knapsack algorithm is constructed to generates the four blocks uniform strip pattern, then the linear programming algorithm is used to generate the cutting plans which iteratively calls the above knapsack algorithm to improve the objective function based on the principle of minimum production cost and changes the current value of punched items to generate a new pattern according to the current value. Lastly, a set of optimal cutting patterns is selected to form the cutting scheme. The algorithm was compared with the famous T-shape algorithm using some benchmark problem tests. The results show that the algorithm can save more sheets than the T-shape one, and the calculation time is reasonable in practical application.