|
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.
|
|
[1]Silva E, Oliveira J F, Wscher G. 2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems[J]. European Journal of Operational Research, 2014, 237(3): 846-856.
[2]Andrade R, Birgin E G, Morabito R. Two-stage two-dimensional guillotine cutting stock problems with usable leftover[J]. International Transactions in Operational Research, 2016, 23(1):121-145.
[3]姜永亮. 基于最优同质块的分段式矩形优化排样[J]. 锻压技术, 2017, 42(7):182-186.
Jiang Y L. Rectangular optimal layout based on segments filled with optimal homogeneous blocks[J]. Forging & Stamping Technology, 2017, 42(7):182-186.
[4]Polyakovsky S, M′Hallah R. An agent-based approach to the two-dimensional guillotine bin packing problem[J]. European Journal of Operational Research, 2009, 192(3): 767-781.
[5]Charalambous C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts[J]. Computers & Operations Research, 2011, 38(10): 1443-1451.
[6]梁秋月, 崔耀东, 游凌伟. 应用三块排样方式求解二维下料问题[J]. 广西师范大学学报：自然科学版, 2014，(3):41-45.
Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns[J]. Journal of Guangxi Normal University: Natural Science Edition, 2014，(3):41-45.
[7]易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法[J]. 锻压技术, 2015, 40(6):150-153.
Yi X Y, Tong Q S, Pan W P. A solving method of two-dimensional cutting for the rectangular blanks [J].Forging & Stamping Technology, 2015, 40(6):150-153.
[8]朱强, 薛峰, 郑仕勇, 等. 约束二维排样问题的一种求解算法[J]. 锻压技术, 2016, 41(9): 148-152.
Zhu Q, Xue F, Zheng S Y, et al. An algorithm of the constrained two-dimensional nesting[J]. Forging & Stamping Technology, 2016, 41(9): 148-152.
[9]Kellerer H，Pferschy U，Pisinger D. Knapsack Problems[M]. Berlin: Springer, 2004.
[10]胡钢, 杨瑞, 潘立武. 基于价值修正的圆片下料顺序启发式算法[J]. 图学学报, 2016, 37(3):337-341.
Hu G, Yang R, Pan L W. Sequential value correction heuristic algorithm for the circle cutting stock problem[J]. Journal of Graphics, 2016, 37(3):337-341.
[11]Belov G, Scheithauer G, Mukhacheva E A. One-dimensional heuristics adapted for two-dimensional rectangular strip packing[J]. Journal of the Operational Research Society, 2008, 59(6):823-832.
[12]呼子宇, 杨景明, 侯新培，等. 基于离散差分进化算法的热连轧批量计划优化[J]. 塑性工程学报，2017，24 (3): 148-153.
Hu Z Y, Yang J M, Hou X P, et al. Optimization of hot rolling batch planning based on discrete differential evolution[J]. Journal of Plasticity Engineering, 2017, 24 (3): 148-153.
[13]Mahori S, Yagiura M, Umetani S, et al. Local Search Algorithms for the Two-dimensional Cutting Stock Problem with a Given Number of Different Patterns[M]. US: Springer, 2005.
[14]Silva E, Alvelos F, Carvalho J M V D. An integer programming model for two-and three-stage two-dimensional cutting stock problems[J]. European Journal of Operational Research, 2010, 205(3): 699-708.
|
Copyright Forging & Stamping Technology.All rights reserved