锻压技术

矩形件单一排样问题的一种精确算法

英文标题：An exact algorithm of the single layout problem for rectangular parts

作者：胡钢孙洪涛潘立武

关键词：矩形件排样整数规划约束规划

分类号：TP391

出版年,卷(期):页码：2016,41(10):43-47

摘要：

针对机械制造业领域的矩形件单一排样问题，即在长宽为L、W的板材里排放最多个数的长宽为l、w的矩形件，提出一种基于整数规划和约束规划的精确排样算法。首先在板材上刻画W+1条等距的水平基线；然后建立单一排样问题的整数规划数学模型，求解出最优排样方案所对应的每条基线上排放的水平矩形件和竖直矩形件个数；最后采用约束规划模型求解出每个矩形件在基线上的具体排放坐标，画出最优排样方案图。将本文算法与文献中的单一排样算法进行比较，结果表明，本文算法求得的板材排样方案中可以排放更多的矩形件，板材利用率更高。

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.

基金项目：

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

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

参考文献：

[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.

服务与反馈：

【本网站尚未开通全文下载服务】【加入收藏】