Transactions of Materials and Heat Treatment

Title：An exact algorithm of the single layout problem for rectangular parts

Authors： Hu Gang Sun Hongtao Pan Liwu

Unit： Sichuan Institute of Information Technology Zhengzhou University of Science & Technology Henan University of Animal Husbandry & Economy

KeyWords： rectangular parts layout integer programming constraint programming

ClassificationCode：TP391

year,vol(issue):pagenumber：2016,41(10):43-47

Abstract：

For the single layout problem of rectangular parts in the mechanical manufacturing field, whose maximum identical rectangular parts (l,w) are put into a sheet (L,W), an exact layout algorithm was proposed based on the integer programming and constraint programming. Firstly, W+1 equidistant horizontal baselines were drawn in the sheet, then an integer programming model was set up, and the maximum number of horizontal items and vertical items on each baseline were confirmed by the most optimizing scheme. Finally, the particular coordination of each item on these baselines was given by the constraint programming model, and a graph of the optimal layout scheme was drawn. Compared the algorithm with other single layout algorithms in the literature, the simulated results indicate that the layout scheme with the algorithm can nest more items in the sheet, and the utilization rate of material is improved.

Funds：

四川省教育厅科研项目（GZY15C45）；河南省科技厅科技攻关项目(152102210320)；河南省高等学校重点科研项目(15B52000)

作者简介：胡钢（1982-），男，学士，讲师 E-mail：rtfdgl@163.com；通讯作者：潘立武（1971-），男，博士，副教授 E-mail：panlw71@163.com

Reference：

[1]Lins L, Lins S, Morabito R. An L-approach for packing (, w)-rectangles into rectangular and L-shaped pieces[J]. Journal of the Operational Research Society, 2003，54（1）: 777-789.

[2]黄永生，钟贤栋，董华军. 集成环境下客车用料优化排样与定额管理[J]. 锻压技术，2014, 39(1)：142-145.

Huang Y S, Zhong X D, Dong H J. Optimal layout and quota management of rail vehicle material under integration environment[J]. Forging & Stamping Technology, 2014, 39(1)：142-145.

[3]易向阳, 仝青山, 潘卫平. 矩形件二维下料问题的一种求解方法[J]. 锻压技术, 2015, 40(6): 150-154.

Yi X Y，Tong Q S，Pan W P. A solving method of two-dimensional cutting for the rectangular blank [J]. Forging & Stamping Technology，2015，40 (6): 150-153．

[4]Cui Y, Zhao Z. Heuristic for the rectangular two- dimensional single stock size cutting stock problem with two-staged patterns[J]. European Journal of Operational Research, 2013, 231(2): 288-298.

[5]Kim K, Kim B I, Cho H. Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry[J]. International Journal of Production Research, 2014, 52(19): 5675-5689.

[6]Morabito R, Morales S. A simple and effective recursive procedure for the manufacturer's pallet loading problem[J]. Journal of the Operational Research Society, 1998，49(8): 819-828.

[7]崔耀东, 张春玲, 赵谊. 同尺寸矩形毛坯排样的连分数分支定界算法[J]. 计算机辅助设计与图形学学报, 2004, 16(2): 252-256.

Cui Y D, Zhang C L, Zhao Y. A continued fractions and branch-and-bound algorithm for generating cutting patterns with equal rectangles [J].Journal of Computer Aided Design & Computer Graphics, 2004, 16(2): 252-256.

[8]Cui Y D, Gu T, Hu W. Recursive algorithms for the optimum cutting of equal rectangles[J]. International Journal of Computers and Applications, 2011, 33(2): 103-107.

[9]杨少杰, 崔耀东. 同尺寸矩形毛坯排样算法[J]. 桂林理工大学学报, 2013, 35(4): 628-630.

Yang S J, Cui Y D. Algorithm for generating cutting patterns of equal rectangular items[J]. Journal of Guilin University of Technology, 2013, 35(4): 628-630.

[10]易向阳, 潘卫平, 张俊晖. 基于五块模式的单一矩形件排样算法[J]. 图学学报, 2015, 36(4): 521-525.

Yi X Y, Pan W P, Zhang J H. Algorithm for generating five block mode cutting patterns of single rectangular items[J]. Journal of Graphics, 2015, 36(4): 521-525.

[11]Young-Gun G, Maing-kyu Kang. A fast algorithm for two-dimensional pallet loading problems of large size[J]. European Journal of Operational Research, 2001, 134(1): 193-202.

Service：

【This site has not yet opened Download Service】【Add Favorite】