第38卷 第4期西南师范大学学报(自然科学版)2013年4月V o l .38 N o .4 J o u r n a l o f S o u t h w e s t C h i n aN o r m a lU n i v e r s i t y (N a t u r a l S c i e n c eE d i t i o n )A pr .2013文章编号:10005471(2013)04008805提高打孔机生产效能的方案设计①郑 文重庆电子工程职业学院,重庆401331摘要:研究了印刷线路板打孔问题,把印刷线路板的过孔问题转换成一个赋权图,成本由作业成本和时间成本构成.钻头的最优行进线路就是要在赋权图中,找一条经过所有点的路且在此路上打孔工序成本最小,以此实现提高打孔机生产效能的方案设计.研究对生产的组织管理㊁打孔作业等问题具有科学的指导意义.关 键 词:赋权图;行进路线;行进时间;刀具切换;成本中图分类号:T H 6文献标志码:A过孔是印刷线路板的重要组成部分之一,打孔机主要用于在制造印刷线路板流程中的打孔作业.研究提高打孔机的生产效能是一个十分重要的问题.图1 某种钻头上8种刀具的分布情况打孔机的生产效能主要取决于以下几方面:1)单个过孔的钻孔作业时间,这是由生产工艺决定,为了简化问题,这里假定对于同一孔型钻孔作业时间都是相同的;2)打孔机在加工作业时,钻头的行进时间;3)针对不同孔型加工作业时,刀具的转换时间.目前,实际采用的打孔机普遍是单钻头作业,即一个钻头进行打孔.现有某种钻头,上面装有8种刀具a ,b ,c , ,h ,依次排列呈圆环状,如图1所示.而且8种刀具的顺序固定,不能调换.在加工作业时,一种刀具使用完毕后,可以转换使用另一种刀具,相邻两刀具的转换时间是18s .作业时,可以采用顺时针旋转的方式转换刀具,也可以采用逆时针的方式转换刀具,将任一刀具转换至其它刀具处,所需时间是相应转换时间的累加.为了简化问题,假定钻头的行进速度是相同的,为180mm /s ,行进成本为0.06元/mm ,刀具转换的时间成本为7元/m i n .刀具在行进过程中可以同时进行刀具转换,但相应费用不减.不同的刀具加工不同的孔型,表1列出了8种孔型所需加工刀具.表1 8种孔型所需加工刀具孔 型A B C D E FG H 所需刀具abcdefgh实际问题中印刷线路板上需要打的孔是成千上万,通过建立数学模型,来解决单钻头作业的最优作业线路(包括刀具转换方案)㊁行进时间和作业成本.表2中象征性地给出了某块印刷线路板过孔中心坐标的①收稿日期:20120826基金项目:重庆市高等教育教学改革研究一般项目(103433).作者简介:郑 文(1966),男,重庆长寿人,副教授,主要从事数学建模的教学与研究.Copyright ©博看网. All Rights Reserved.24个数据,单位是密尔(m i l )(也称为毫英寸,1i n c h =1000m i l),以此说明模型的可行性.表2 过孔中心数据孔型A孔型B孔型CX1000Y 243600X-142269Y 271474X152000Y 321800X -10000Y 301000X -142269Y 290371X 152800Y -282200X -142200Y326000X -142269Y302970X 155000Y290600孔型D 孔型E 孔型FX -142269Y 251471X -142269Y-312418X -15600Y 221600X 132267Y -270351X 132267Y -315568X -157800Y 325000X -141169Y263325X -112264Y 318718X-157932Y246000孔型G 孔型HX 102269Y-309269X -145400Y 287200X 142269Y 300418X -145418Y 262025X290600Y155000X-145418Y2714741 问题分析在印刷线路板的过孔问题中,钻头的最优作业线路设计应使行进时间和作业成本尽可能小,这是一个多目标优化问题.由于钻头的行进时间是有成本的,把行进时间换算成时间成本,所以总成本应是时间成本与作业成本之和,这样就把多目标优化问题变成了单目标优化问题.把线路板上的任意两个孔v i ㊁v j 相连,以V ={v 1,v 2, ,v n }为顶点集,边E ={e =v i v j |孔v i 与v j的连线},每一条边上对应着一个权c (e ),权由作业成本和时间成本构成,则(V ,E ,c)就构成了一个赋权图N [1].钻头的最优作业线路问题就转化为在赋权图N 中,寻找一条经过V 中所有点的路,且在这条路上总成本达最小.2 从一孔到另一孔打完所需的成本2.1 两孔之间钻头的行进成本及行进时间设孔v i (x i ,y i )㊁v j (x j ,y j ),从孔v i (x i ,y i )到v j (x j ,y j )的距离d i j =25.41000(x i -x j )2+(y i -y j )2距离d i j 中25.41000是把单位毫英寸转化为毫米.钻头的行进成本是0.06元/mm ,所以从孔v i (x i ,y i )到v j (x j ,y j )钻头的行进成本是c ᶄi j =0.06d i j (元)钻头的行进速度是v =180mm /s ,所以从孔v i (x i ,y i )到v j (x j ,y j )钻头的行进时间是t ᶄi j =d i j v =d i j180(秒)2.2 刀具的切换时间及切换成本为了研究的方便,对刀具a ㊁b ㊁ ㊁h 编号,用数字1㊁2㊁ ㊁8来表示.由于钻头既可顺时针旋转也可逆时针旋转,所以从刀具i 到刀具j 与从刀具j 到刀具i 所用时间相同,刀具切换时间矩阵A 是一个对称矩阵,即有A (i ,j )=A (j ,i );另一方面与刀具i 等距离的刀具切换时间相同;由于相邻刀具的切换时间是18s,所以从刀具i 到刀具j 的切换时间算法如下:1)在i ɤj 的情况下.当j ɤ5+i -1时,A (i ,j )=18(j -i );当j >5+i -1时,A (i ,j )=A (i ,2(4+i )-j ).2)在i >j 的情况下,A (i ,j )=A (j ,i ).用MA T L A B 语言编程求解,得刀具切换时间矩阵A =(a i j )8ˑ8,切换时间表如下(单位:s ):19第4期 郑 文:提高打孔机生产效能的方案设计Copyright ©博看网. All Rights Reserved.表2 刀具的切换时单位:sabcdefgh a 018365472543618b 180183654725436c 361801836547254d 543618018365472e725436180183654f 547254361801836g 365472543618018h183654725436180由于刀具切换的成本是7元/m i n,所以由刀具i 切换到刀具j 的成本是b i j =a i j60ˑ7(元)所以刀具切换成本矩阵B =760A .2.3 从v i (x i ,y i )到v j (x j ,y j )的孔打完所需的时间成本设孔v i (x i ,y i )用的刀具对应编号是m ,孔v j (x j ,y j )用的刀具对应编号是n ,则由孔v i (x i ,y i )到孔v j (x j ,y j )刀具的切换时间是A (m ,n ).影响从一孔到另一孔打完所需时间的因素有3个:钻孔时间㊁钻头行进时间㊁刀具切换时间;由于假设钻孔时间相同,所以我们只考虑钻头行进时间㊁刀具切换时间.又因钻头在行进时可进行刀具切换,所以从v i (x i ,y i )到v j (x j ,y j )的孔打完所需的时间就是钻头行进时间与刀具切换时间的最大者t i j =m a x (t ᶄi j ,A (m ,n ))由于钻头的行进速度为180mm /s ,行进成本为0.06元/mm ,所以时间成本为180mm /s ˑ0.06元/mm =10.8(元/s)故从v i (x i ,y i )到v j (x j ,y j )的孔打完所需的时间成本是c ᵡi j =10.8t i j (元)2.4 从v i (x i ,y i )到v j (x j ,y j )的孔打完所需成本影响从一孔到另一孔打完所需成本的因素有四个:钻孔成本㊁钻头行进成本㊁时间成本㊁刀具切换成本;由于假设钻孔成本相同,所以我们只考虑钻头行进成本㊁刀具切换成本㊁时间成本;钻头行进成本与刀具切换成本之和称为作业成本.设孔v i (x i ,y i )用的刀具对应编号是m ,孔v j (x j ,y j )用的刀具对应编号是n .由前面的分析知,由孔v i (x i ,y i )到孔v j (x j ,y j )刀具的切换成本是B (m ,n ),行进成本是c ᶄi j =0.06d i j ,时间成本是c ᵡi j =10.8t i j .所以从v i (x i ,y i )到v j (x j ,y j )的孔打完所需的成本为c i j =c ᶄi j +c ᵡi j +B (m ,n )即钻头行进成本㊁时间成本㊁刀具切换成本之和.3 打完所有孔的最小成本这里不妨以v 1为起点,D 表示从v 1出发,经过赋权图N 中所有点的路径P 之集,C (P )表示在路径P 上的成本,即C (P )=ðPc i j ;T (P )表示在路径P 上的加工时间,即T (P )=ðPt i j ;则得如下模型[1]m i n C (P )P ɪ{D求解算法[2-3]设计如下:设S ⊂V ,S =V -S .29西南师范大学学报(自然科学版) h t t p ://x b b jb .s w u .c n 第38卷Copyright ©博看网. All Rights Reserved.1)S =φ,C ѳ0,T ѳ0.2)S ѳS ɣ{v 1}.3)设点v i ɪS ,求顶点v j ,v j ɪS ,使c i j =c (v i v j )=m i n v k ɪS{c (v i v k )}同时,记录以下信息:C ѳC +c i j 累计成本T ѳT +t i j累计时间s t r ѳᶄv i (m )ңv j (n )ᶄ记录刀具转换4)S ѳS ɣ{v j },S ѳS -{v j }.5)若S =φ,则停止;否则转3).路径P 就是集合S 中元素加入的顺序v 1ңv ᶄ2ңv ᶄ3ң ңv ᶄn路径P 上对应的成本C 就是以v 1为起点经过赋权图N 中每一个点的所有路中的最小成本.对表2中提供的数据,以(1000,243600)为起点,按上述算法,用MA T L A B 语言编程[4]求解,得以v 1为起点,加工完所有孔的最小成本是9187.9元,行进时间是531.978s .4 打完所有孔的最小成本很显然,只要起点不同,按前面的算法,得到的打孔线路就不同,成本也就不一样;为此我们要去寻找使成本最小的路的起点.我们把赋权图N 中的每一个点与v 1交换,执行程序,即将程序循环n 次,得以每一个点为起点,线路板打孔工序的成本向量C B =(C 1,C 2, ,C n )所以得线路板打孔工序的最小成本C =m i n (C B )=m i n (C 1,C 2, ,C n )C 对应路P 的起点就是最优的打孔起点.对表2中提供的数据编程求解,得以赋权图N 中各点为起点对应的最小成本:C B =[9187.9 9181.5 9373.8 8950.1 9036.5 8998.1 8329.7 8867.5 8326.99040.2 9054.8 9057.2 8152.2 9301.2 9164.8 9187.8 9117.0 9056.29010.1 8727.9 8662.8 8835.8 8797.5 8826.3]C =m i n (C B )=8152.2(元)最小值C =8152.2在第13个位置上;所以应选择以点v 13(-142269,-312418)为起点,运行程序,得在印刷线路板的过孔问题中,钻头的最优作业线路设计方案,如表3所示.表3 钻头行进路线㊁刀具切换方案㊁运行成本㊁运行时间序号xy刀具切换累计成本/元累计时间/s 1-142269-312418e 2102269-309269e ->g 766363132267-315568g ->e 1205724132267-270351e ->d 1471905152800-282200d ->c 17031086290600155000c ->g 31881807142269300418g ->g 38212098-156********g ->f 43612349-112264318718f ->e478125439第4期 郑 文:提高打孔机生产效能的方案设计Copyright ©博看网. All Rights Reserved.49西南师范大学学报(自然科学版)h t t p://x b b j b.s w u.c n第38卷10-157800325000e->f5047272续表3钻头行进路线㊁刀具切换方案㊁运行成本㊁运行时间序号x y刀具切换累计成本/元累计时间/s11-157932246000f->f528828312-142269251471f->d570731913-141169263325d->d574332014-142269271474d->b614835615-142269290371b->b620635916-142269302970b->b624436117-142200326000b->a647637918-145400287200a->h673239719-145418271474h->h678039920-145418262025h->h680840021-10000301000h->a7240420221000243600a->a741842923155000290600a->c805746524152000321800c->c8152469总的最小成本8152.1元.其中作业成本3087.7元,时间成本5064.4元,其行进时间468.9s.现实问题中,印刷线路板上需要过的孔成千上万,把线路板的过孔问题转化成一个在赋权图中找最短路问题,实现最优线路的方案设计,以此提高过孔效能.本文的研究对生产的组织管理㊁打孔等问题具有科学的指导意义.参考文献:[1]韩伯棠.管理运筹学[M].3版.北京:高等教育出版社,2010:232-243.[2]程辉,李晓辉,姚兵.连通多叶图的几种标号[J].西南大学学报:自然科学版,2011,33(10):92-95.[3]胡继宽,汪维清.一种适宜于海量数据的快速分组排序算法[J].西南大学学报:自然科学版,2010,32(186):173-175.[4]赵静,但琦.数学建模与数学实验[M].3版.北京:高等教育出版社,2009:182-184.D e s i g n f o r I m p r o v i n g t h eE f f i c i e n c y o fP u n c h e rP r o d u c t i o nZ H E N G W e nC h o n g q i n g C o l l e g eo f E l e c t r o n i cE n g i n e e r i n g,C h o n g q i n g401331,C h i n aA b s t r a c t:I no r d e r t o i m p r o v e t h ee f f i c i e n c y o f p u n c h e r p r o d u c t i o n,t h e p r o b l e m o f p r i n t e dc i r c u i tb o a r d d r i l l i n g i s s t u d i e d i n t h i s p a p e r.T h e p r o b l e mv i a p r i n t e dc i r c u i tb o a r d i s c h a n g e d i n t oaw e i g h t e d g r a p h. T h e c o s t c o n s i s t s o f t h e o p e r a t i o n c o s t a n d t h e t i m e c o s t.T h e b e s t r o u t e o f t h e b i t i s t o f i n d i n t h ew e i g h-t e d g r a p ha p a t h t o a l l p o i n t s a n d t om i n i m i z e t h e c o s t o f t h e p u n c h i n gp r o c e s s.K e y w o r d s:w e i g h t e d g r a p h;t r a v e l l i n g r o u t e;t r a v e l l i n g t i m e;k n i f e s w i t c h i n g;c o s t责任编辑汤振金Copyright©博看网. All Rights Reserved.。