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

An exact algorithm of the single layout problem for rectangular parts

作　　者：胡钢[1] 孙洪涛[2] 潘立武[3] 

机构地区：[1]四川信息职业技术学院信息工程系,四川广元628017 [2]郑州科技学院管理信息中心,河南郑州450064 [3]河南牧业经济学院自动化与控制系,河南郑州450011

出　　处：《锻压技术》2016年第10期43-47,共5页Forging & Stamping Technology

基　　金：四川省教育厅科研项目(GZY15C45);河南省科技厅科技攻关项目(152102210320);河南省高等学校重点科研项目(15B52000)

摘　　要：针对机械制造业领域的矩形件单一排样问题,即在长宽为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.

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

分 类 号：O221[理学—运筹学与控制论]