经验交流 机电工程技术 !""# 年第 $% 卷第 $ 期 机电工程技术 !""# 年第 $% 卷第 $ 期 剩余矩形匹配算法在矩形件排样中的应用 曾凤华 （广州航海高等专科学校， 广东广州 %&"$$"） 摘要：介绍了剩余矩形匹配算法，并将其应用到任意矩形件的优化排样上，较好地解决了矩形件板材的排料问题。 关键词：剩余矩形匹配算法；矩形件；优化排样 中图分类号：’(&)"*+ 文献标识码：, 文章编号：&""-.-)-! /!""#0 "$.""#)."! & 引言 矩形件排样优化一 般 是 指 在 给 定 的 板 材 上 按 一 定 要 求 排放尽可能多的所需矩形件 ， 使 排 放 区 域 的 板 材 废 料 尽 可 能少，以提高板材的利用率 。 这 是 许 多 行 业 迫 切 需 要 解 决 的 问 题 ， 如 以 金 属 材 料 作 为 主 要 原 材 料 的 制 造 行 业 ， 玻 璃、塑料、家具等制造行业 。 如 果 矩 形 件 板 材 排 料 采 用 手 工试算或凭经验下料和排料 ， 那 么 原 材 料 利 用 率 不 高 ， 成 本 增 加 且 工 作 效 率 低 ， 尤 其 是 企 业 进 行 大 规 模 定 制 生 产 时，手工试算排料几乎不可 能 。 因 此 ， 提 高 板 材 的 利 用 率 和板材排料的速度是许多行 业 亟 待 解 决 的 问 题 ， 毛 坯 的 下 料生产是产品零部件制造过 程 中 的 第 一 道 工 序 ， 其 组 织 方 式和排样效率对产品的生产 周 期 和 成 本 有 很 大 的 影 响 。 板 材排样优化问题实际上是一 个 十 分 困 难 的 问 题 ， 从 数 学 计 算 复 杂 性 理 论 可 知 ， 它 属 于 12（134567689:4:;7:< 23=>43? 9:@= 的缩写，即非确定型的多项式算法）类问题 ［&］。至今 人们无法找到一种多项式算 法 ， 只 能 用 有 效 的 近 似 算 法 求 解 ［!］。近似算法是求其局部最优的近似解，其计算结果虽 然 达 不 到 最 优 解 ， 但 接 近 最 优 解 ， 比 人 工 排 样 的 效 率 高 ， 能达到人们所期望的材料利 用 率 。 本 文 着 重 讨 论 近 似 算 法 中的剩余矩形匹配算法在矩形件排样中的应用。 ! 剩余矩形匹配算法 剩余矩形匹配算法 是 一 种 动 态 的 局 部 寻 优 算 法 。 即 在 排样过程中，按一种给定的 寻 优 规 则 ， 在 板 材 上 的 某 个 矩 形内排放选定的矩形件，同 时 也 不 断 地 在 板 材 上 产 生 一 些 较 小 的 矩 形 ， 然 后 又 用 那 些 未 排 的 矩 形 件 来 填 充 小 矩 形 ， 直到所有的矩形件被排完为止。排样的基本约束条件是： （&）任意两个矩形件之间不能互相重叠； （!）矩形件不能排出板材之外； （$）保证板材切割时满足通裁的要求。 具体方法如下：设 原 料 的 左 下 角 和 右 上 角 的 坐 标 分 别 收稿日期：!""%—&"—!) #) ，"" ）、 （!& 为 （!" 形的左下角开始。若下料零件 @& 则 下 料 后 的 剩 余 矩 形 为 ［（!"A!! ""A"! ）， （!& ，"& ，"& ）， 所 有 下 一 个 下 料 点 都 是 以 剩 余 矩 、"! ）］、 ［（!" 的长宽尺寸分别为 !! ，"" ）］。 如图 & 所示。 ）， （!& ，"& ， ， 图 & 排样运算图 第一次下料后出现 两 块 矩 形 。 若 再 进 行 一 次 下 料 ， 必 须从中选定一块。当选中一 块 后 ， 采 用 启 发 式 的 方 法 重 新 分块。 因 此 ， 在 第 # 次 切 割 完 成 后 ， 一 共 剩 余 #A& 个 矩 形 。 从 #A& 个矩形中选择下一个矩形下料的原则是：零件的长 度尽可能的接近矩形的长度 和 宽 度 （设 定 矩 形 和 零 件 的 长 度 总 是 不 小 于 宽 度 ）。 首 先 算 出 零 件 的 长 度 与 #A& 个 矩 形 的 长 度 或 宽 度 的 比 值 ； 然 后 选 择 最 大 的 比 值 所 对 应 的 矩 形。如果将矩形长边分为水 平 或 垂 直 两 种 情 况 ， 则 零 件 的 排样方案有四种，如图 !。 $ 实验结果与结论 （&）实验结果 本 文 通 过 上 述 的 近 似 算 法 编 制 了 计 算 机 程 序 ， 并 在 %+# 微 机 上 进 行 了 实 现 ， 具 体 操 作 流 程 见 图 $。 下 面 利 用 

机电工程技术 !""# 年第 $% 卷第 $ 期 机电工程技术 !""# 年第 $% 卷第 $ 期 经验交流 经编程验算，得出的排样图，如图 & 所示。 图 ! 零件在矩形上的排样方案 本 算 法 对 一 个 实 例 进 行 验 证 。 给 定 板 材 的 长 为 !&""’’， 宽为 (!""’’，需排样零件长、宽及数量如表 ( 所示。 （)） （-） 图 $ 系统操作流程图 表 ( 矩形零件数量与尺寸 零件代号 零件数量 零件长 （’’） 零件宽 （’’） 5 6 7 8 9 : ; < ’ = > ! ! ! ! ! & & & . & & ("$" 0." 0!" 0!" #." ("$" #&" &%" &%" $&" $!" 0!" %!" &#" ." &"" &#" $&" $"" ("" ((" ("" （/） 图 & 零件的排样图 从排样图可以看出该实例总共使用了三块原材料来排放 所需零件， （)）图的材料利用率为 *$+%,， （-）图的材料 利用率为 .*+.,，（/）图的材料利用率为 0*+%,。通过其它 实验表明，这种方法对数量更多的矩形件排样效果更好。因 此其排料利用率和速度已大幅度提高，达到了降低成本，提 高劳动生产率的目的，增强企业在市场上的竞争力。 参考文献： ［(］曹炬+ 实 用 矩 形 件 优 化 排 样 系 统 的 研 究 与 开 发 ［1］+ 锻 压 技 术，(***， （$）：(*2!$+ ［!］ 方 仍 存 ， 曹 炬 ， 陈 学 松+ 矩 形 件 优 化 排 样 的 一 种 近 似 算 法 ［1］+ 锻压技术，!""$， （#）：(*2!(+ 作者简介：曾凤华，女，(*## 年生，湖南沅江人，讲师，硕士研 3编辑：向 飞4 究生。研究领域：机械工程。 #% 

$%&’(%&’ )’*+&,-*./0 $%&’(%&’1!2"3"0 4%*’56 !"#$%&’$( 7’ 5889*&: ;&.%<: =<, :&-*>’*’> .%& *;8&99&, <= 5 ;*?&: =9<@ 8A;8 *- 8,<8<-&:B C%*- ;&.%<: *- D5-&: <’ .%& .,5E :*.*<’59 :&-*>’*’> 8,59 8A;8-0 @%*F% *- >&’E $&+&,59 G&/ 85,5;&.&,- -AF% 5- &?*. &,599/ A-&: *’ .%*- =*&9:B @*:.% 5’: ,5:*A- <= .%& *;8&99&,0 5’: &?*. 5’>9& <= D95:&- 5,& ,&+*-&: D5-&: <’ .%& 5’59/-*- <= -<;& &?F&99&’. %/:,5A9*F ;<:E &9- <= ;*?&: =9<@ 8A;8-B )*+ ,-%.#( ;*?&: =9<@ 8A;8H *;8&99&,H :&-*>’ !!"#!$#%! &’( )(*(+,- ./012,+’3 14 56+’ 5/6**,*0 7(+’18 412 719,/( :191+ /0!1 23456 78 93* I$F%<<9 <= J&F%5’*F59 K L9&F.,*F59 L’>*E ’&&,*’>0 4$)0 4%5’>-%5 #!""2M0 4%*’56 !"#$%&’$( 7 G*’: <= 85.% 895’’*’> ;&.%<: D5-&: <’ >&’&.*F 59E ><,*.%; =<, ;&’&B N’ .%& =*.’&-- =A’F.*<’ F<’.5*’- &?89*F*. 8%/-*F ;&5’- .%& ;&.%<:0 5’: F<,,&-8<’:*’> ;A.5.*<’ <8&,5.<, *- 8,<+*:&:0 -< .%5. O7 F5’ D& 9&5: .< 5’ <8.*;*(&: ,&-A9. ,58*:9/B C%& &?8&,*;&’. -%<@- .%5. .%*- 59><,*.%; F5’ >&. 5 <8.*;59 85.% =5-. 5’: -.&5:/B )*+ ,-%.#( ;&’&.*F 59><,*.%;H 85.% 895’’*’> $F%<<9 <= OA5’>:<’> )’*+&,-*./ !!"#!$#%; <(=,0* 6*8 :(=(62-’ 14 +’( >+2?-+?26/ 14 @21==# 26,/ ,* +’( 5/6*(2 &AB( 76-’,*(= /81 :;<&4=>346 /0 ?<&4=4*45 IJ&F%5’*F59 K L9&F.,*F59 L’E >*’&&,*’> <= C&F%’<9<>/0 OA5’>(% 85,.- <= .%& 895’&, ./8& ;5F%*’&-0 .%& RA59*./ <= .%& F,<--Q,5*9S- -.,AFE .A,59 F5’ D&&’ :*,&F.9/ 5==&F.&: <’ .%& 8&,=<,;5’F& <= .%& ;5E F%*’&- 5’: .%& F<-. <= ;5F%*’*’>B N’ .%*- 858&, .%& ,&-&5,F% *- .%& =<,; <= :<’& 5D <= >A*:&Q@5/0 5’: .%& :*-FA--*<’ *- >*+&’ 5D .%& =*’*.& &9&;&’. 5’59/-*- ;&.%<:0 .%& F<;89&?*<’ <= -.*==’&-- 5DA*:& Q@5/ :*-.,*DA.*’> *- F<’.,5-.&:B )*+ ,-%.#( .%& 895’&, ./8& ;5F%*’&-H F,<--Q,5*9H >A*:&Q@5/H -.*== ,*D 5’: -&F.*<’0 =<,;- <= [,+?8A 14 +’( 5(241236*-( 14 D1*0 &,3(#<(E /6A(8 @1*+21/ >A=+(3 F=,*0 G6H(/(+ &26*=4123 .*6/A=,= 7(+’18 @*45 A34 =+<&4B6 A<* ?-45 =>3&45C I!BU&’5’ L9&F.,*F59 5’: J&F%5’*F59 7F5:&;/0 V&85,.;&’. <= 7A.<;5.*F 4<’.,<90 W*’?*E 5’>#1M""X0 4%*’5H XBU&’5’ N’=<,;5.*<’ L’>*’&&,*’> 4<99&>& 0LE :AF5.*<’59 7:;*’*-.,5.*<’ Y5FA9./0 Z%&’>(% .%& -/-.&;-B C%& 8,*’F*89& <= [NV F<’.,<9 -/-.&; *- -*;89& 5’: .%& =A’F.*<’ *- , <-F*995.*<’ -.5.& D&F5A-& <= D5: .A’*’> *’ 5FE .A59 895’.-B .,5’-=<,; .< 8, 9<’> .*;&Q:&95/&: ]<*’.H 8, \5+&9&. %<@&+&,0 !!"#!$#;% <(H(/1B,*0 14 F*,H(2=6/ >(2,6/ I?= <(H,-( <2,HE (2 J,+’ G<7 :DEF G&456 H!FG ?3&4=;-45 IY5FA9./ <= J&F%5’*F59 K !"# L9&F.,<’*F L’>*’&&,*’>0 4%*’5 )’*+&,-*./ <= O&<-F*&’F&-0 \A%5’ #M""^#0 4%*’56 !"#$%&’$( )’*+&,-59 $&,*59 TA- I)$T6 *- A-&: @*:&9/ D&F5A-& <= .%& 5:+5’.5>&- <= F<’+&’*&’F&0 %*>%&, -8&&: 5’: [9A> 5’: [95/ YA’F.*<’0 5’: *. %5- D&F<;& 5 8<8A95, *’.&,=5F& D&.@&&’ F<;8A.E &, 5’: 8&,*8%&,59 :&+*F&B )$T :,*+&, *- .%& -<=.@5,& *’.&,=5F& D&E .@&&’ .%&; @%*9& \*’:<@- V,*+&, J<:&9 *- .%& 95.&-. .%& )$TXB" -8&F*=*F5.*<’0 &-8&F*599/ = :,*+&, ;<:&9B Y*,-.0 <’ .%& .,5’-=&, ./8& 5’: DA- 8,<.’ ;&.%<: <= )$T :,*+&, *- 85,.*FA95,9/ *’.,<:AF&:B 7. 95-. .%& 5889*F5.*<’ D&.@&&’ [4 5’: )$T :&+*F& *- >*+&’B )*+ ,-%.#( \VJH )_TH )$TVN I\VJ6 !!" #!$ #"! &’( <(H(/1B3(*+ 14 K*+(//,0(*+ @1*+21/ >A=+(3 412 L/(H6+12 18 I;*IOA5’>(%(%&’. &9&+5.<, F<’.,<9B V*==&,&’. @*.% .%& .,5:*.*<’ -/-.&;0 *. :<&- ’<. ’&&: 5 85,599&9 F<’’&F.<, @%*F% F<’’&F.- @*.% *’.&99*E >&’. -/-.&; 5’: F<’.,<9 -/-.&;0 -5+&- ,&-*+&- .%& @5/ .< ,&59E F5’ D& 5:+5’F&:B N’ 5::*.*<’0 *(& .%& -/-.&;B )*+ ,-%.#( &9&+5.<,H *’.&99*>&’. F<’.,<9H J[) !!" #!$ #"M N,0’ 52(-,=( >(/4 #B?*-+?6/ @/1-O >+?8A 9A )/196/ 51=,+,1*,*0 >A=+(3 :(-(,H(2 ID!FG A3&4=5-45I$F%<<9 <= J&F%5’*F590 L9&F.,<’*F 5’: 4<’E .,<9 L’>*’&&,*’>0 T&*]*’> a*5<.<’> )’*+&,-*./0 T&*]*’>!"""##0 4%*E ’56 !"#$%&’$( C%& F9’59 8,<+*:&: D/ O9 $/-E .&; IO[$6 *- @*:&9/ A-&: 5- 5 -/’F%,<’ .&9&+*-*<’ -/-.&; 5’: &9&F.,*F 8<@&, -/-.&; 5’: .%& :*-895/ <= .*;& *’ 8AD9*FB aA8*.&, X! O[$ _&F&*+&, 5’: .%& *’=<,;5.*<’ ,&95.&: .< .*;& 5,& *’.,<:AF&:0 5’ 7CJ&>53#‘ ;*F,% 8,&F*-& -&9=Q8A’F.A59 F9*+&’B C%& ,&-A9. -%<@- .%5. .%& 5885,5.A- F5’ F<;89&.&9/ ;&&. .%& ’&&: <= 5889*F5.*<’B )*+ ,-%.#( O[$H ;*F,53#‘H -&9=Q8A’F.A59 +’( 76+( ./012,+’3 14 >?2B/?= !!" #!$ #"% .BB/,-6+,1* 14 :(-+6*0/( 1* +’( D6A1?+ 14 :(-+6*0/( 562+= IEFG 7*45 =;<& IOA5’>(%&0 1!"MM"0 4%*’56 !"#$%&’$( N’ .%*- 858&,0 *. -*;89/ *’.,<:AF&- .%& ;5.& 59><,*.%; <= -A,89A- ,&F.5’>9&0 5’: 5889*&- .< .%& <8.*;A; 95/9& 85,.-B C%& FA..*’> -.AE 95, D9<,*.%; <= -A,89A- ,&F.5’>9&H OA5’>(%9& !!"#!$#PQ <(=,0* 14 &(3B(26+?2( :(8?-+,1* 6*8 8?=+B2114 14 <(=O+1B @13B?+(2 @69,*(+ ID!1 :;*45=;<&B6 /08 93&4=J3-45B6 ?1FG K<=>3&4C I!B Y5FA9./ <= J&F%5’*F59 5’: L9&F.,*F59 L’>*’&&,*’>0bA’;*’> )’*E +&,-*./ <= $F*&’F& 5’: C&F%’<9<>/0 bA’;*’> 31""PM0 4%*’5H XB $%&’/5’> c<,;59 )’*+&,-*./0 $%&’/5’> !!""M#0 4%*’56 !"#$%&’$( D/ 8<*’.*’> .%& 8, +*,.A59 :&-*>’ .&F%’<9<>/ 5’: %&5. 8*8& .&F%’<9<>/0 .%& -.,AF.A,& <= :&-G.<8 F<;8A.&, F5D*’&. 5’: :*-8&99*’> ;<:& 5,& :&-*>’&:B 4<;8A.&, F5D*’&. D&F<;&- 5’ 5DE N’ .%& 858&,0 !"#$%!&$#