A Hybrid Sequential Heuristic Procedure to One-dimensional CSP

Abstract

Abstract:

This paper proposed an improved hybrid sequential heuristic procedure for one-dimension CSP.The algorithm modified the subset selection strategy of original sequential heuristic procedure and avoided the ending condition in the limited time with width search algorithm,and could change the parameters according to the users' maximum time patience dynamically.Finally C# was used to realize the algorithm.the results show the algorithm is effective.This algorithm were used in Ma'anshan Steel Corp,wheel company official for more than two years,and increases the cutting rate 4%.

Key words: cutting stock problem(CSP), dynamic programming, sequential heuristic procedure, knapsack problem

摘要：

针对一维下料问题，提出一种改进的混合顺序启发式算法。该算法修正了传统顺序启发式算法的待切子集选择策略，采用广度搜索算法在有限时间内解决终止条件问题，根据用户最大时间容忍度动态地改变参数。最后采用C#进行编程,实现了该算法,通过对比证明算法的有效性。该算法在马鞍山钢铁公司车轮分公司正式使用了两年多,使切割率提高4%。

关键词: 下料问题, 动态规划, 顺序启发式算法, 背包问题

CLC Number:

N945.15

Cheng Hao, Liu Xinbao, Fang Chang. A Hybrid Sequential Heuristic Procedure to One-dimensional CSP[J]. China Mechanical Engineering, 2014, 25(16): 2191-2195,2203.

程浩, 刘心报, 方昶. 基于混合顺序启发式算法的一维下料问题[J]. 中国机械工程, 2014, 25(16): 2191-2195,2203.

References

[1]Gilmore C P,Gomory E R.A Linear Programming Approach to the Cutting Stock Problem[J].Operations Research, 1961,9(6):848-859.
[2]Gilmore C P,Gomory E R.A Linear Programming Approach to the Cutting Stock Problem,Part Ⅱ[J].Operations Research, 1963,11(5):863-888.
[3]Dyckhoff H.A Typology of Cutting and Packing Problems[J].European Journal of Operational Research, 1990, 44(2):145-159.
[4]Gradiar M, KljajiC' M,ResinoviC G,et al.A Sequential Heuristic Procedure for One-dimensional Cutting[J].European Journal of Operational Research,1999,114(3):557-568.
[5]Gradiar M,ResinoviC G,KljajiC' M.A Hybrid Approach for Optimization of One-Dimensional Cutting[J].European Journal of Operational Research,1999,119(3):719-728.
[6]Song X,Chu B C,Nie Y Y,et al.An Iterative Sequential Heuristic Procedure to A Real-Life 15-dimensional Cutting Stock Problem[J].European Journal of Operational Research,2006,175(3):1870-1889.
[7]曹炬,刘毅,凌少东.可焊接的一维排样问题的一种启发式算法[J]．中国机械工程，2007,18（2）:135-138．
Cao Ju,Liu Yi,Lin Shaodong.A Heuristic Algorithm of One-dimensional Cutting Stock Problem While Items Can be Joined[J]. China Mechanical Engineering,2007,18(2):135-138．
[8]阎春平,刘飞,刘颖,等.基于ASP模式的多软件协同优化下料方法及其实现技术[J].中国机械工程,2002,13（24）:2144-2147．
Yan Chunping,Liu Fei,Liu Ying,et al.Multi-software Collaboration Cutting-stock Method Based on ASP and Its Implementing Technologies[J].China Mechanical Engineering,2002,13(24):2144-2147.
[9]Gradisar M,Peter T.A Combined Approach to the Solution to the General One-dimensional Cutting Stock Problem[J].Computers & Operations Research,2005,32(7):1793-1807.
[10]Cui Yaodong.A CAM System for One-dimensional Stock Cutting[J].Advances in Engineering Software,2012,47(1):7-16.
[11]刘睿,于波,崔耀东.一维下料问题中提高计算效率方法的研究[J].计算机工程与应用,2013,49（9）:247-250．
Liu Rui,Yu Bo,Cui Yaodong.Several Heuristic Strategies to Improve Computational Efficiency for One-dimensional Cutting Stock Problem[J].Computer Engineering and Applications,2013,49（9）:247-250．
[12]Cherri C A,Arenales N M,Yanasse H H.The Usable Leftover One-dimensional Cutting Stock Problem-a Priority-in-use Heuristic[J].International Transactions in Operational Research,2013,20(2):188-199.
[13]靳鹏,马华伟,杨善林.考虑订购成本的多目标一维下料优化模型[J]．系统工程学报，2013, 28（1）:19-27．
Jin Peng,Ma Huawei,Yang Shanlin.Considering Stock Ordering Cost Multiple Objectives Optimal Model of One-dimensional Cutting Stock[J].Journal of Systems Engineering,2013,28(1):19-27.
[14]Yamada T.Some Exact Algorithms for the Knapsack Sharing Problem[J].European Journal of Operational Research, 1998,106(1):177-183.
[15]Gradiar M,Jesenko J,Resinovi C G.Optimization of Roll Cutting in Clothing Industry[J].Computers & Operations Research,1997,24(10): 945-953.