文档介绍：矩形件排样优化贪婪算法及系统开发
Vo l112 No11 第 12卷 第 1期 哈 尔 滨 理 工 大 学 学 报
Feb. , 2007 2007年 2月JOURNAL HARB IN UN IV. SC I. & TECH.
于零 前采用较多的方法是设计相应的近似算法来求得其 件种类和个数的减少 ,有可能产生非常大的余料. 动
[ 5 ]近似最优解 . 目前国内外学者对矩形件优化排样问 态算法 根据一种局部最优原则 ,不断动态地产生 收稿日期 : 2006 - 03 - 18
( ) 作者简介 : 宋连超 1981 - ,男 ,哈尔滨理工大学硕士研究生.
待排点p、 ,然后对这些小矩形区域排样 , 1 2
同时也消去一些已排过的矩形区域 ,直至所有的矩
形件被排完为止. 这种算法由于划分矩形区域规则
的局限性 ,在排样后期可能会使板材上的矩形件排
布不合理 ,满足不了实际生产中切割工艺的要求. 本
[ 6 - 7 ] 文在总结矩形件排样优化近似算法 基础上 ,提 出一种新的排样算法 ,即贪婪算法 . 实验结果表明 , 图 1 横排和纵排示意图
本文的贪婪算法使板材上的矩形件排布更趋合理 、 ( ) (设待排点 p坐标为 px, y板材起始排样 0 0 0 0 更加规则 ,不仅满足了实际生产中切割工艺的要求 , (ΔΔ) ( 点 坐 标 为 p/ 2,/ 2 , p、p的 坐 标 为 px, 0 1 1 1 2 1 1 又能够有效提高板材利用率. ) ( ) y、px, y, 则由图 1可知 : 1 2 2 2
x= x 10
2 贪婪算法 (Δ ) + w +s y = y 1 0 j 2 j 或 Δ x= x+ l+ 20j 2设排样所用板材的长为 L , 宽为 W. 所有要排的 y = y 2 0 矩形件一共有 k 种 , 第 i种矩形件的长为 l, 宽为 w , i i x= x 10( ) 个数为 n1 ?i?k . 排样的基本目标为 :使板材的 i Δ+ l + y = y 1 0 j 2 ( )3 利用率尽可能的高. 排样的约束条件为 :矩形件之间 (Δ ) x = x + w +s 2 0 j 2 j 不能有相互重叠的区域 , 并且矩形件不能有排出板 y = y 2 0 材之外的部分 . 排样规则为 :能横排就不竖排 . 板材 ( ) 式中 , 前一种为横排 , 后一种为纵排 . 由 px, y、 1 1 1 的利用率为 ( ) px, y可以推导出与这两个排样点对应的待排 2 2 2 k ( ) ( ) 区域 R: u, v、R: u, v的长 、宽分别为1 1 1 2 2 2 lw si i i? i = 1u = x - x η ( )= m ax 1 1 2 1 LW Δ 1( ) 式中 , s0 ? s? n是一个非负整数 , 表示排样方 v= W - y- i i i 11 2 ( )4 案中第 i种矩形件在板材上排放的个数. Δ 1 u= L - x- 贪婪算法总是做出在当前看来是最好的选择 , 22 2 希望通过每次所作的最好选择来得到问题的一个最 v = y - y 2 2 1 优解. 针对矩形件优化排样问题 , 贪婪算法的排样规 下一步对这两个待排区域进行排样. 将待排区 则就是每次排样时都排放面积最大的矩形件 , 以此 域 { R } 按照面积由小到大的顺序进行排序 , 然后选 t
来实现板材利用率最高的目标. 因此 , 将所有矩形件 择其中面积最小的 待排 区域 作 为新 的“母 板 ”S = 按照面积由大到小的顺序进行 排序 并保 存 在链 表 m in{ R } , 同时将该待排矩形区域的长 u 、宽 v 替代 t t t 中 , 然后按照这个次序依次对矩形件进行排样. 计算式中原始母板的长 L、宽 W , 与待排矩形件进行
首先 , 从母板的左下角开始排放第一种面积最 可排性判别 . 如果 L ? l, W ? w , 当前待排矩形件 j j 大的矩形件 r, 初始化排样次数 j = 1, 排放的个数为 1 可以进行横排 ; 如果 L ? w , W ? l, 当前待排矩形 j j ΔW - 1 件可以进行纵排 . 对于这两种情况 , 都按前述方法继 in t? n ΔjW- 1 Δw+ in t j 2 续排放矩形件 , 见图 2 b. 若不满足以上两种情况 , 则 Δw + ( )2 s= j 2j ΔW - 1重新选择下一个面积稍大的待排区域 , 进行可排性 in t > n jn jΔw + j 2判别 . 这样 , 每进行一次排样都会产生两个新的待排 ( ) ΔΔ式 2 中 ,为矩形件