一维下料问题的一种混合启发式算法

A Hybrid Heuristic Algorithm for the One Dimensional Cutting Stock Problem

讨论一维下料问题,即用库存线材原料切割出若干种已知数量和长度的零件,优化目标为最大化线材利用率。提出一种混合启发式下料算法,用当前零件构造线材所有可能的切割方式,计算每种切割方式的废料长度、零件平均长度、大零件数量,按照废料最小、零件平均长度最大、大零件数量最多的原则选择一种切割方式切割相应线材,满足部分零件需求;用剩余零件继续构造线材可能的切割方式,按上述原则继续选择相应线材进行切割,重复该过程,直到所有零件的需求量得到满足为止。采用文献中基准例题验证文中下料算法,数值实验结果表明该算法与4种文献算法相比性能占优,且算法计算时间合理。

It discuss the one dimensional cutting stock problem,that is to use the stock rods to cut out a set of items with specified length and demand,the optimization goal is to maximize the utilization of rods. A hybrid heuristic algorithm is presented,the algorithm generates all possible cutting patterns using the current items,calculates the wastage,average length of parts and the number of large part of each cutting pattern,selects a cutting pattern to cut corresponding rod to meet some parts demands,in accordance with the principle of minimum waste,maximum average length of parts and maximum number of large parts. Continue to construct the possible cutting pattern using the remaining parts and cut the corresponding rods in accordance with the above principle,repeats the process until all demand of the parts was satisfied. The literature benchmark instances was used to validate the propose algorithm,numerical experiments show that the algorithm performs better than four published algorithms for improve material utilization,and has a reasonable computing time.