解决二维下料问题的顺序启发式算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (13): 234-237.

解决二维下料问题的顺序启发式算法

黄少丽，杨剑，侯桂玉，崔耀东

广西师范大学计算机科学与信息工程学院，广西桂林 541004

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-01 发布日期:2011-05-01

Sequential heuristic algorithm for two-dimensional cutting stock problem

HUANG Shaoli，YANG Jian，HOU Guiyu，CUI Yaodong

School of Computer Science，Guangxi Normal University，Guilin，Guangxi 541004，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-01 Published:2011-05-01

摘要/Abstract

摘要： 求解二维下料问题即求解如何用最少的板材排入所需的全部毛坯的问题。一种基于价值修正策略的顺序启发式算法被用来生成排样方案，方案中的排样方式按单位面积价值最大生成，在各排样方式顺序生成的过程中不断修正方式中使用到的毛坯的价值。迭代调用该过程多次生成多个排样方案，从中选择最优的排样方案。通过实验证明算法的有效性。

关键词: 二维下料, 占角动作, 穴度, 顺序价值修正, 顺序启发式算法

Abstract: The two-dimensional cutting stock problem is a problem about how to minimize the material input to pack all the blanks required.A sequential heuristic algorithm based on the value correction strategy is presented to generate cutting stock plan.Patterns in the plan are generated sequentially according to the maximum unit value and the values of blanks assigned to the current pattern are adjusted.Several solutions are constructed iteratively and at last the best one is selected.The computational results show the effectiveness of the presented algorithm.

Key words: two-dimensional cutting, corner-occupying action, caving degree, Sequential Value Correction（SVC）, Sequential Heuristic Procedure（SHP）

黄少丽，杨剑，侯桂玉，崔耀东. 解决二维下料问题的顺序启发式算法[J]. 计算机工程与应用, 2011, 47(13): 234-237.

HUANG Shaoli，YANG Jian，HOU Guiyu，CUI Yaodong. Sequential heuristic algorithm for two-dimensional cutting stock problem[J]. Computer Engineering and Applications, 2011, 47(13): 234-237.

[1]	张雨，崔耀东，梁泽华. 多尺寸圆木二维下料问题研究[J]. 计算机工程与应用, 2018, 54(19): 266-270.
[2]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.
[3]	刘睿1，于波1，崔耀东2. 一维下料问题中提高计算效率方法的研究[J]. 计算机工程与应用, 2013, 49(9): 247-250.
[4]	陈端兵黄文奇. 求解矩形和圆形装填问题的最大穴度算法[J]. 计算机工程与应用, 2007, 43(4期): 1-3.