|
Abstract：
|
|
To discuss the guillotine cutting problem of rectangle piece in machinery manufacturing field, a cutting algorithm based on recursive partitioning was proposed. With two cutting line that perpendicular to each other and with T shape, the plate was divided into three sub plates, in which the lower left corner sub plate was called layout block,and the remaining two sub plates were called recursive blocks. For layout block, rectangle piece was discharged in a simple way, and for the recursive block, it was considered as plates to be divided. The implicit enumeration algorithm was used to determine the optimal pattern of the layout block, and the optimal rectangle type and the number of rows and columns of rectangles in the block were obtained. The branch and bound algorithm was used to determine whether the recursive block continues to be divided or not. The benchmark instances are used to compare the proposed algorithm with the literature algorithms. Experimental results show that the proposed algorithm is superior to the literature algorithms in the pattern value, and the computation time can meet the practical use.
|
|
Funds：
|
|
广西自然科学基金资助项目（2015GXNFBA139264）;广西教育厅科研项目（KY2016YB610）
|
|
AuthorIntro：
|
|
沈萍（1974-），女，硕士，实验师
E-mail：jsgxdgb@163.com
|
|
Reference：
|
［1］Delorme M, Iori M, Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms
［J］. European Journal of Operational Research, 2016, 255(1): 1-20.
［2］Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems
［J］. Computational Optimization and Applications, 2001, 18(1): 63-88.
［3］ 扈少华，潘立武，管卫利. 复合条带三阶段排样方式的生成算法
［J］.锻压技术，2016，41（11）：149-152.
Hu S H，Pan L W，Guan W L. A generating algorithm of three-stage nesting patterns for composite strip
［J］. Forging & Stamping Technology，2016，41（11）：149-152.
［4］ Cui Y. A new dynamic programming procedure for three-staged cutting patterns
［J］. Journal of Global Optimization, 2013, 55(2):349-357.
［5］ Cui Y. Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns
［J］. Computers & Operations Research, 2008, 35(1):212-225.
［6］ 潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的矩形件最优三块布局算法
［J］. 图学学报, 2015, 36(1): 7-11.
Pan W P, Chen Q L, Cui Y D, et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks
［J］.Journal of Graphics, 2015, 36(1): 7-11.
［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］. 〖JP3〗广西师范大学学报：自然科学版, 2014, (3):41-45.〖JP〗
Liang Q Y, Cui Y D, You L W. Solving two-dimensional cutting stock problem with three-block patterns
［J］. 〖JP3〗Journal of Guangxi Normal University: Natural Science Edition, 2014, (3):41-45. 〖JP〗
［9］ Cui Y D. Heuristic for two-dimensional homogeneous two-segment cutting patterns
［J］. Engineering Optimization, 2013, 45(1):89-105.
［10］ Chen Q, Cui Y, Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns
［J］. Optimization Methods & Software, 2016, 31(1):68-87.
［11］ Young-Gun G, Seong Y J, Kang M K. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems
［J］. Operations Research Letters, 2003, 31(4):301-307.
|
|
Service：
|
|
【This site has not yet opened Download Service】【Add
Favorite】
|
|
|
|
Copyright Forging & Stamping Technology.All rights reserved