矩形件剪切下料问题的一种顺序价值修正算法  

A sequential value correction algorithm for cutting stock problem of rectangular part

作　　者：沈萍[1] 邓国斌[1] Shen Ping;Deng Guobin(Department of Computer and Electronic Information Engineering, Guangxi Vocational ＆ Technical College, Nanning 530226, Chin)

机构地区：[1]广西职业技术学院计算机与电子信息工程系

出　　处：《锻压技术》2018年第4期180-184,共5页Forging & Stamping Technology

基　　金：广西自然科学基金资助项目(2015GXNFBA139264);广西教育厅科研项目(KY2016YB610)

摘　　要：针对矩形件剪切下料问题,提出一种基于顺序价值修正策略的优化下料算法。首先构造普通块排样方式的生成算法,生成矩形件在单张板材上的排样方式。然后采用顺序价值修正算法,调用上述排样算法,逐个生成排样方式,每个排样方式满足部分矩形件的需求量,直到所有矩形件的需求量均被满足为止,在生成每个排样方式后按照一定规则修正这个排样方式中矩形件的价值。最后将上述顺序价值修正算法迭代执行多次得到多个下料方案,选择耗费板材张数最少的作为最终解。使用基准例题将本文算法与两种文献算法进行对比实验,结果表明,本文算法在节省板材方面优于两种文献算法,且计算时间合理。For the cutting stock shearing problem of rectangular part,an optimal cutting stock algorithm based on sequential value correction strategy was proposed. Firstly,the generation algorithm of ordinary nesting type was constructed,and the nesting type of rectangular part on single plate was generated. Then,by the sequential value correction algorithm,the above algorithm was invoked to generate nesting types one by one,and every nesting type met the demands of some rectangular parts,the operation was terminated until the demands of all rectangular parts were satisfied. After generating every nesting type,the value of rectangular part in this nesting type was corrected according to a certain rule. Finally,the above sequential value correction algorithm was executed and iterated repeatedly to obtain multiple cutting stock plans,and the cutting stock plan which consumed the minimum number of plates was chosen as the final solution. The algorithm was compared with two algorithms from literatures by benchmark examples. The results show that the proposed algorithm is superior to two algorithms from literatures in term of saving plates and reasonable calculation time.

关 键 词：剪切下料问题 普通块排样方式 顺序启发式算法 价值修正 矩形件 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]