打孔机生产效能的提高.doc

论文题目： D 打孔机生产效能的提高 组 别：本科D题：打孔机生产效能的提高摘要过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。想要提高打孔机的生产效能，可通过优化路径来减小钻头的行进路程和刀具转换次数。针对上述问题进行建模，有两种解决方案，即单钻头路径选择优先模式和单钻头刀具转换方式优先模式。每种模式均先应用贪心算法对路径进行求解，再用TSP优化圈方案优化加工路径。对于双钻头问题，由于作业时两个钻头相互独立，并且有合作间距的限制，因此在解决双钻头最优作业方案时，我们只需在单钻头作业的基础上再加上另一个钻头作业所需的各种费用并增加约束条件，保证合作间距在要求范围内即可。由单钻头的两种优化方案的执行结果得知，刀具转换优先模式明显优于路径选择优先模式，所以我们在双钻头问题中只用刀具优先模式。结果得到双钻头打孔在时间和费用上均优于单钻头打孔，可对双钻头的使用进行推广。 关键词：生产效能 贪心算法 TSP优化圈方案 路径选择优先 刀具转换优先一、 问题重述随着电子科技的发展，印刷线路板的需求量越来越大，怎样降低线路板的成本成为人们关注的问题，因此提高打孔机的生产效能至关重要。打孔机的生产效能主要取决于三方面：单个过孔的钻孔作业时间、作业时钻头的行进时间、针对不同孔型作业时刀具的转换时间。目前采用的打孔机普遍是单钻头作业。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，且顺序不能调换，如图1所示。bcdefgha图1：某种钻头上8种刀具的分布情况作业时，采用顺时针或逆时针的方式转换刀具，相邻两刀具的转换时间是18 s，将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为简化问题假定钻头的行进速度相同，为180 mm/s，行进成本为0.06元/mm，刀具转换时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一块线路板加工完成后才能制作另一线路板，但同一线路板上过孔加工只保证刀具加工次序正确即可。需要解决的问题如下：（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是1/100密尔（mil）（1英寸=1000 mil），1英寸=2.54cm。给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。（2）为提高打孔机效能，设计一种双钻头打孔机，两钻头可以同时作业且相互独立，但过孔加工必须保持两钻头间距不小于3cm（称为合作间距）。（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究两钻头合作间距对作业路线和生产效能产生的影响。二、 模型假设1.假设对于同一孔型钻孔作业时间相同；2.假设打孔机的钻头和所要加工的孔均视为一个质点；3.假设打孔机的行进是匀速的；4.假设钻头在行进时进行刀具转换，由于换刀时间远大于行进时间，故取刀具转换时间，不计钻头行进时间。三、 符号说明四、 问题分析印刷线路板过孔加工时间及费用由以下三个因素决定:1、 单个过孔的作业时间；2、 打孔机钻头行进路程；3、 针对不同孔型加工作业时，刀具转换时间；路径选择优先方案着重在所有的孔中寻找一条最短路径，使其遍历各孔，且不重复，然后根据过孔需要进行相应的刀具转换。刀具转换优先方案着重寻找换刀次数最少的换刀方案，然后根据各刀具的不同对原始孔族进行重新划分和重组，使各刀具依次在其相应的孔族作业，作业完毕进行换刀，直到所有孔族全部加工完毕。分析各孔型所需刀具及加工次序，共8种刀具且全都使用过，则刀具转换至少为7次。而孔型所需刀具加工顺序有cf和fc的存在，则换刀次数至少要加3次。由上述可得如下刀具转换方案：defghabcdef，换刀次数为10次。问题一：最优作业方案就是要使总加工费用最小。单个过孔的钻孔作业时间是由生产工艺决定的，因此最优作业方案只由2、3两个因素决定。刀具转换时间和刀具转换费用由换刀次数决定，钻头行进时间和行进费用由作业路径的选择决定。因此，寻找最优作业方案的目标就成为设计钻头最短行进路线，同时使换刀次数最少。钻头行进时间越小，换刀次数越少，加工总费用越小，作业路线最优，效率越高。问题二：由问题一的结果得知，刀具转换优先模式明显优于路径选择优先模式，因此此问题只采用刀具转换优先解决。五、 模型建立问题一：有路径选择优先和刀具转换优先两种模式，均先用贪心算法找出一条路径，再用TSP优化圈方案进行优化。有：加工总费用=钻头行进费用+刀具转换费用Z2加工总时间=钻头行进时间+刀具转换时间建立优化模型 , , 问题二：两个钻头使用相同的刀具在指定孔族作业，直到该孔族所有孔加工完毕，两钻头同时换刀至下一孔族。，则 六、 算法的理论分析一、 贪心算法在孔族中选第一个孔为作业起点，记为，在剩余的孔中找距最近的孔作为第二个要加工的孔，记为，依此类推，直至最后一个孔。此时形成一个待加工的孔的序列，如下：，至此贪心算法对孔的加工序列排序完毕。二、 TSP优化圈算法 对序列,若存在i,j,当jn时满足，当j=n时满足，则序列变为或。重复上述操作，至无法找到满足上述条件的i,j终止。七、 模型求解整个过程均用Matlab编程问题一的求解：（1）对于单钻头路径优先模式，结果如下：行进总距离D1：2.6290e+007合6677.66mm行进有效距离D2：1.5470e+007合3929.38mm（用于计算作业时间）换刀次数n：2566行进时间t1:37.0980s换刀时间t2:46188s合12.83h作业时间t3：4.6210e+004s合12.8361h行进费用s1：400.6585元换刀费用s2：5388.6元作业成本s3：5.7893e+003=5789.3元路径如下图：（2）对于单钻头刀具优先模式，结果如下：行进总距离D1：8.9576e+007合22752.304mm行进有效距离D2：8.5519e+007合21721.826mm换刀次数n：12（由加工终点回到加工起点需再换刀两次）行进时间t1:126.4016s合2.1min换刀时间t2:216s合3.6min作业时间t3：336.6774s合5.6113min行进费用s1：1.3651e+003=1365.1元换刀费用s2：25.2元作业成本s3：1.3903e+003=1390.3元路径如下图：刀具转换优先模式的生产效能明显优于路径选择优先模式，因此在生产中采用刀具转换优先模式。问题二：（1）双钻头打孔结果如下：行进距离：7.7439e+007合20012.66mm换刀次数：24换刀时间：216s合3.6min作业时间：296.0474s合4.95613min有效行进时间：80.0474s合1.35613min行进费用：1180.2元换刀费用：50.4元作业费用：1230.6元路径如下图：不同颜色线条代表不同钻头作业路径。双钻头与传统单钻头进行比较：钻头缩短的作业时间为：336.6774s-296.0474s=40.63s；由于换刀时间相同，则钻头缩短的有效行进时间和缩短的作业时间相同；钻头减少的行进费用为：1365.1 -1180.2= 184.9元；刀具转换增加的费用为：50.4-25.2=25.2元；钻头减少的总的作业费用为：1390.3-1230.6=159.7元。有上述比较可知，双钻头打孔较传统单钻头生产效能确有提高，应推广使用。 （2）两钻头合作间距限制着两钻头能否很好的独立作业。由于其限制，使得在选择作业路径时钻头二的选孔对钻头一具有很强的依赖性，造成所选路径并不是最优的，直接导致行进时间的增长和行进成本的增加。若能改善工艺，使两钻头的干扰距离缩短，即合作间距减小，则确定的作业路线会更优，生产效率会更高。七、模型优缺点模型优点1、模型是分不同模式计算，对比鲜明。2、本文的模型简单，其算法直观，容易编程实现。3、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。模型缺点在建模与编程过程中，很多假设只是为了简化问题，因而得出的结果可能与现实情况有一定的差距。参考文献1肖仁彬，陶振武.孔群加工路径规划问题的进化求解 J.计算机集成制造系统，2005,11（5）：682-6892党林立，孙晓群.数学建模简明教程M.西安：西安电子科技大学出版社，20093宣明.数学建模与数学实验M.浙江：浙江大学出版社，20104王树乐.数学模型选讲M.北京：科学出版社，2008 5吴启迪，汪镭，智能蚁群算法及应用M.上海：上海科技教育出版社，20046玄光男，程润伟.遗传算法与工程优化M.北京：清华大学出版社，20037周正武，丁同梅.基于TSP和GA孔群加工路径优化问题的研究，组合机床与自动化加工技术，2007（7）：30-32附件问题一.(1) 路径优先模式 %贪心算法N=2124;%孔的总数定义为常量Nfor i=1:N-2; d1=sqrt(a(i+1,1)-a(i,1)2+(a(i+1,2)-a(i,2)2); %第i+1个孔和第i个孔之间的距离 x=a(i+1,1);y=a(i+1,2);z=a(i+1,3); %a(i,3)为孔的类型标记，分别将ABCDEFGHIJ孔型定义为1 2 3 4 5 6 7 8 9 10 m=i+1; for j=i+2;N; d2=sqrt(a(j,1)-a(i,1)2+(a(j,2)-a(i,2)2); if d2d1 m=j; end end a(i+1,1)=a(m,1); %进行距离最近孔的交换 a(i+1,2)=a(m,2); a(i+1,3)=a(m,3); a(m,1)=x; a(m,2)=y; a(m,3)=z;end%旅行商问题优化圈求解for i=1:N-1 j=N; while i=j if jd2 for m=1:i b(m,1)=a(m,1); b(m,2)=a(m,2); b(m,3)=a(m,3); end h=j; for m=i+1:j b(m,1)=a(h,1); b(m,2)=a(h,2); b(m,3)=a(h,3); h=h-1; end for m=j+1:N b(m,1)=a(m,1); b(m,2)=a(m,2); b(m,3)=a(m,3); end a=b; end end if j=N d3=sqrt(a(i+1,1)-a(i,1)2+(a(i+1,2)-a(i,2)2); d4=sqrt(a(j,1)-a(i,1)2+(a(j,2)-a(i,2)2); if d3d4 for m=1:i b(m,1)=a(m,1); b(m,2)=a(m,2); b(m,3)=a(m,3); end h=j; for m=i+1:j b(m,1)=a(h,1); b(m,2)=a(h,2); b(m,3)=a(h,3); h=h-1; end a=b; end end j=j-1; endenda(N+1,:)=a(1,:);x=a(:,1);y=a(:,2);plot(x,y,g-)hold on;plot(x,y,r.)hold offtitle(单钻头打孔最优路径图)i=1;D1=0; %行进的总路程while(i=N) D1=D1+sqrt(a(i+1,1)-a(i,1).2+(a(i+1,2)-a(i,2).2); i=i+1;endD2=0; %钻头行进有效距离(计算总时间是应用）i=1;while(i=N) if a(i,3)=a(i+1,3) D2=D2+sqrt(a(i+1,1)-a(i).2+(a(i+1,2)-a(i,2).2); end i=i+1;endn=0; %换刀次数m1=1; %打完第一个孔的刀具种类i=2;while i4 %比较两刀具之间转换次数确定换到的方向 n=n+8-abs(m1-m2); else n=n+abs(m1-m2); end m1=m2; case 2 m2=2; if abs(m1-m2)4 n=n+8-abs(m1-m2); else n=n+abs(m1-m2); end m1=m2; case 3 m2=1; if abs(m1-m2)4 n=n+8-abs(m1-m2)+2; else n=n+abs(m1-m2)+2; end m1=3; case 4 if abs(m1-4)4 p=8-abs(m1-4); else p=abs(m1-4); end if abs(m1-5)4 q=8-abs(m1-5); else q=abs(m1-5); end if pq m2=5; if abs(m1-5)4 n=n+8-abs(m1-5)+1; else n=n+abs(m1-5)+1; end m1=4; end if p4 n=n+8-abs(m1-4)+1; else n=n+abs(m1-4)+1; end m1=5; end case 5 m2=3; if abs(m1-m2)4 n=n+8-abs(m1-m2)+3; else n=n+abs(m1-m2)+3; end m1=6; case 6 if abs(m1-7)4 p=8-abs(m1-7); else p=abs(m1-7); end if abs(m1-8)4 q=8-abs(m1-8); else q=abs(m1-8); end if pq m2=8; if abs(m1-8)4 n=n+8-abs(m1-8)+1; else n=n+abs(m1-8)+1; end m1=7; end if p4 n=n+8-abs(m1-7)+1; else n=n+abs(m1-7)+1; end m1=8; end case 7 m2=4; if abs(m1-m2)4 n=n+8-abs(m1-m2)+4; else n=n+abs(m1-m2)+4; end m1=6; case 8 m2=8; if abs(m1-m2)4 n=n+8-abs(m1-m2); else n=n+abs(m1-m2); end m1=m2; case 9 m2=5; if abs(m1-m2)4 n=n+8-abs(m1-m2)+2; else n=n+abs(m1-m2)+2; end m1=3; case 10 m2=6; if abs(m1-m2)4 n=n+8-abs(m1-m2)+3; else n=n+abs(m1-m2)+3; end m1=3; end i=i+1;endaD1 %行进总距离D2 %行进有效距离N %换刀次数t1=D1/100.0/1000*2.54*10/180 %行进时间t2=18*n %换刀时间t3=D2/100.0/1000*2.54*10/180+18*n %总的作业时间s1=D1/100.0/1000*2.54*10*0.06 %行进费用s2=n*18*7/60.0 %换刀费用s3=s1+s2 %总的作业成本（2）单钻头刀具转换优先模式N=232,222,29,54,40,1448,788,404,115,0;%将各孔族的孔的个数存在N中%k=cat(1,a1,a2,a3,a4,a5,a6,a7,a8,a9);将各孔族拼接整合H=1;K=N(1);for n=1:9 %贪心算法 for i=H:K-2; d1=sqrt(k(i+1,1)-k(i,1)2+(k(i+1,2)-k(i,2)2);%第i+1个孔和第i个孔之间的距离 x=k(i+1,1);y=k(i+1,2); m=i+1; for j=i+2;K; d2=sqrt(k(j,1)-k(i,1)2+(k(j,2)-k(i,2)2); if d2d1 m=j; end end k(i+1,1)=k(m,1);%进行距离最近孔的交换 k(i+1,2)=k(m,2); k(m,1)=x; k(m,2)=y; end %旅行商问题优化圈求解 for i=H:K-1 j=K; while i=j if jd2 p=i+1;q=j; while pd4 p=i+1;q=j; while pq x=k(p,1);y=k(p,2); k(p,1)=k(q,1); k(p,2)=k(q,2); k(q,1)=x; k(q,2)=y; p=p+1;q=q-1; end end end j=j-1; end end H=H+N(n);K=K+N(n+1);end N1=0;for i=1:9 N1=N1+N(i);endk(N1+1,:)=k(1,:);x=k(:,1);y=k(:,2);plot(x,y,g-)hold on;plot(x,y,r.)hold offtitle(单钻头打孔最优路径图)D1=0;%行进的总路程i=1;while(i=N1) D1=D1+sqrt(k(i+1,1)-k(i,1).2+(k(i+1,2)-k(i,2).2); i=i+1;endD2=0;%钻头行进有效距离(计算总时间是应用）H=1;K=N(1);for n=1:9 i=H; while(i1 dmin1=sqrt(a1(1,1)-h(m-1,1)2+(a1(1,2)-h(m-1,2)2); x=1; for j=2:N(1) D2=sqrt(a1(j,1)-h(m-1,1)2+(a1(j,2)-h(m-1,2)2); if D21 n1=1; for i=1:N(1) D1=sqrt(a1(i,1)-h(m-1,1)2+(a1(i,2)-h(m-1,2)2); if D1=118110.2362 r(n1,:)=a1(i,:); n1=n1+1; end end if i=N(1) dmin2=sqrt(r(1,1)-k(n-1,1)2+(r(1,2)-k(n-1,2)2); y=1; for i=2:n1-1 d=sqrt(r(i,1)-k(n-1,1)2+(r(i,2)-k(n-1,2)2); if d=11