Abstract: The two-dimensional cutting stock problem with exact two-staged patterns is solved to minimize the plate cost to meet the blank demands. The approach combines the sequential heuristic procedure and a pattern-generation algorithm to generate the patterns of the cutting plan sequentially. It uses the value-correction strategy to adjust the values of the included blanks after each pattern is generated. Multiple cutting plans are generated through iteration, and the best of them is selected. Experiments are carried out to compare the proposed approach with both commercial stock-cutting software package and published algorithms. The results show that the proposed approach is most effective to reduce plate cost.

Key words:  two-dimensional cutting, uniform strip, two-staged pattern, sequential value correction, sequential heuristic procedure

摘要： 求解基于精确两阶段排样图的二维下料问题，用最小的板材成本，生产出所需要的全部毛坯。将顺序启发式算法和排样图生成算法相结合，顺序生成排样方案中的各个排样图；采用顺序价值修正策略，在生成每个排样图后修正其中所含各种毛坯的价值。经过多次迭代生成多个排样方案，从中选择最好者。实验计算时与商业软件和文献算法相比较，结果表明所述算法可以更为有效地减少板材消耗。

关键词: 二维下料, 均匀条带, 两阶段排样, 顺序价值修正, 顺序启发式算法