毕业论文（设计）-打孔机生产效能的提高.pdf

期8L砌烂窗阳倒隔高论文一:打孔机生产效能的提高 摘要本文就打孔机生产效能的提高，运用jave和分析法建立数学模型，针对实际问 题，分别考虑两条原则：，路径和转换方式最优原则，时间最优原则建立模型。由于两个问题都为优化问题，我们用类似最小生成树方法求解钻头行进路程的最 短路径，以图论结合的方法分析最优刀具转换方式。针对问题一，根据题目提供的印刷线路板过孔中心坐标数据，我们利用matlab画 出了坐标分布图（见附录）。分析其点分布，发现dlelflglhla3ble 这种刀具转换方式不仅能保证每个点都打到且转换次数最少，这样就不仅降低了转换 成本,而且也使转换时间缩小到最少的。运用java程序模仿最小生成树设计快速算 法，求出各种孔型各自分布点的最短路径及路径的首尾坐标。根据各种孔型之间的打 孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第一点坐标相连，即得到钻头行进的最优路径。经过我们的反复计算，最终行进总路程为1633.72cm,行 进时间为1727.21 s,作业成本为1001.23元。对于问题一，我们仿照问题二分区域的方法，进行了优化，用牺牲刀具的转动 时间来做到减短钻头所行总路线，将其划分为三个区域，钻头根据区域依次行走，经 过计算得出最终行进总路程为1475.96 cm,行进时间为2086.33s,作业成本为948.58 元，相比原本的方法，此种方法虽时间稍微多一些，但钻头行进路程变短了，也降低 了成本。针对问题二，由于是双钻头的打孔机，且作业是独立的，但为避免钻头间的触 碰和干扰，我们采取了分区域的做法，即两个钻头分开作业。根据分析，决定将其 分为四个区域并根据各个区域各种孔型分布特点，求出最短刀具转换方式，除了其中 第二个区域是fig玲hlalblcldlelf,其余皆为,求解方法与问题一相似，经过统计和计算，最终 行进总路程为1407.86m,行进时间为1534.32s,作业成本为924.516元。与单钻头 比较时间效率提高了 552.01s,缩短了钻头的行进路程，成本降低了 24.06元。关键字：java matlab 最小生成树1.问题的提出打孔机主要用于制造印刷线路板流程中的打孔作业。为提高生产效能，需 进行合理的作业安排，设计加工一块线路板的最优计划，需考虑以下几个方 而：单个过孔的钻孔作业时间，这是由生产工艺决定；打孔机在加工作业时，钻头的行进时间；针对不同孔型加工作业时，刀具的转换时间。在给定的某种砖头，上面装有8种刀具a,b.c,h,依次排列呈圆环状，如图 1所示：a.。b-c。d+g+图1：某种钻头8种刀具的分布情况而且8种刀具的顺序固定，不能调换。加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间为18so作业时，可采用顺（逆）时针旋转的方式转换刀具。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为简化问题，假定钻头的行进速度是相同的，为 180mni/s,行进成本为0.06元/mm,刀具转换的时间成本为7元/min。刀具在 行进过程中可以同时进行刀具转换，但相应费用不减。不同刀具加工不同孔型，表一列出了 10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表L 10种孔型所需加工刀具及加工次序同一线路板上的过孔不要求加工完毕一个孔，再加工令一个孔，即对于须用 两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c要求：根据提供的数据给出单钻头的最优作业线路（包括刀具转换方案）、行进时间 和作业成本；设计一种双钻头的打孔机，（每个钻头的形状与单钻头相同），两钻头可以 同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻 头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔 加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作 业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。2.问题分析问题（一）分析：本题为优化问题，主要是考虑钻头行进的成本和时间，以及转换刀具的成 本和时间，找到走遍所有点的最优路径，使得打孔机的生产效能达到最高。根据题目提供了印刷线路板过孔中心坐标的数据，我们利用matlab画出了 坐标分布图（见附录1）。发现同种孔型，有分布集中的，也有分布较为分散 的。又由于钻头行进速度，行进成本和刀具转换时间成本不变，因此只要尽可 能找到钻头行进的最短路程及求出刀具的最少转换次数即可。为确定钻头行进的行进路程，我们采用了类似最小生成树的方法，求出各 种孔型各自分布点的最短路径及路径的首尾坐标。通过画图与分析，找到了最 优的刀具转换方式，并因此确定各种孔型之间的打孔顺序。最后根据各种孔型 之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第 点坐标相连，即得到钻头行进的最优路径。问题（二）分析：本题的主要问题与问题一差不多，也是要求打孔机的最高生产效能。印刷线路板过孔中心坐标的数据与问题一一样，不同的是，本题是双钻头 的打孔机（每个钻头的形状与单钻头相同），且作业是独立的，但为避免钻头 间的触碰和干扰，在过孔加工的任何时间必须保持两钻头间距不小于3cm。基 于这两个条件，我们采取了分区域的做法，即两个钻头分开作业，这样就能够 很好地避免钻头间的触碰和干扰。由点的分布图分析，最终分成四块区域，按 照区域分布特点，确定刀具转换方式与各种孔型之间的打孔顺序。按照问题一 的方法依次求出各个区域最短行进路程，加总即为最路程。3.模型假设（1）打孔时的时间设为每打一次为0.5s；钻头行进过程平稳，不发生故障;钻头行进灵活，可自由改变方向;钻头行进速度是相同的；相邻刀具转换时间是固定的；钻头看作质点。4.定义与符号说明钻头行进的路程1.加工一块板所需时间Q.加工一块板总的成本21.钻头行进的成本02.刀具的转换成本c.刀具的转换次数tQ.打一个孔所用时间，设为常量0.5秒孔.表示打孔的次数Pi.刀具行进的单价（元/mm）P2.转换刀具的单价（元/min）V.钻头行进的速度Qi.对应下标区域钻头的行进成本i=l,2,3）Sk.对应区域内钻头的行进路程k=l,2,3）s7.按顺序不同刀具行进的路程s打.第i个刀具转到第j个刀具时所走的路程K.第k个钻头所走的路程九.第k个钻头的刀具转换时间k=l,2出.第k个刀具打到的钻孔的个数k=l,24.转换刀具所花费的时间2钻头的行进时间3打孔时间5.模型建立与求解问题一：(-)模型的分析与建立：求最短距离时，我们采用了类似最小生成树的原理。例如：若有五个顶点1,2,3,4,5,原理如下：图E图D原理说明：从图A各条路径中选出最短路径，即2,顶点为3和4,标记顶点3 和顶点4,连接最短路，得到图B；接着以顶点3和4为顶点，找出与顶点3和 4相连的最短路，即为3,顶点为2和3,并作标记，连接最短路，得到图C；如此一来，顶点3被标记两次，视为无效点(即不可再被标记)，接着以顶点2和4为顶点或相反方向。同理可得图iyE,最半。短路径3最优化刀具转换方式分析：虽然孔型A和孔型B的数量占据了很大一部分，但是由于它们都是单刀具 型的，对钻头转换方式没什么影响。另外，虽然钻型D和钻型F需要两种刀 具，但是它们并没有要求顺序，对钻头转换方式也基本没有什么大的影响，所 以我们去除了孔型A、B、D和F,优先考虑其他孔型。在不考虑单钻头和没有次序限制的钻孔下，对剩下的钻孔的钻头转换进行 详细列出，得图2：图2：钻头转换方式分析图孔型G需要有三种刀具，所以我们选择优先考虑孔型G的钻头转换方式，通过与其他钻孔钻头进行比较（由图2中箭头体现），我们确定了一条比较理 想的钻头转换方式线路：dlefffghabcdef又根据确定的刀具转化方式，我们可以确定各种孔型之间的打孔顺序，如图3 所示：方框对应一个位置上的刀具，的头表示执行项号.空方框表示其对应的刀具没有打孔图3：打孔顺序排列因为在刀具转换的时候，钻头本身还可以保持移动，且钻头的移动速度非 常快，所以图上两个空方框之间就无需再考虑时间问题，即只需考虑其转换时 间。因此：成本二转换刀具的花费+每个时期对应刀具的钻头行进路程的花费即:Min Q=Ql+Q2T=%+%3c+1 c c+1s=Si+ESui=l i=l j=2q、HV。2=52 60%=18。St?=一V3=0表L各种孔型最短路径的端点坐标及路径的相关信息(二)模型的求解：运用类似最小生成树的方法，用java设计程序(见附录2),求得钻头行 走各种孔型最短路径的各个端点坐标及路程，见表1：孔型端点一坐标(x,y)(cm)端点二坐标(x,y)(cm)路程(cm)时间(s)A-3.082.526.8518.92153.998.5B-5.99-1.50-7.3818.94304.2816.9C8.0613.758.92-1.66217.2312.1D-7.1112.872.2623.36134.027.5E1.0521.382.243.2597.985.4F0.1221.262.3421.2666.173.68G-8.16-1.585.1422.6734.131.89通过比较坐标图中所有钻孔线路的端点，获得每种刀具及转换时所走的路 程，如下表所示：H8.062.78-8.119.9423.731.32I12.4515.5712.4521.5136.392.02J-6.82-1.6611.3714.54144.406.36表二：使用各刀具所走路程及其他相关信息刀具为孔型所 需要最短路程(所 有孔点及不同 孔点之间的 和)(cm)转换下一 刀具的路 程(cm)路程之和(cm)时间(s)打的孔数(个)dGD153.330153.338.51232eDI155.6112.68168.299.34222fJ114.4010.08124.486.9129gGF77.812.9280.734.4854hFH71.609.2680.864.4940aAC320.771.11321.8817.881030bB304.284.40308.6817.14787cCJIE278.330278.3315.46404d000e000fEG117.140117.146.5115合计：1633.7290.712913结果:tl=18*10=180st2=90.71st3=2913*0.5=1456.5sT=tl+t2+t3=1727,21sS=1633.72cmQ=006*10*163372+(10*18)760*7=1001.23(元)问题一的优化:为了优化问题：我们设计了分区域打孔，从坐标图我们肉眼直观的分为三 个区域，第一区域为x-5cm,y不限制的长方形区域，第二部分为-5cmx,且 y15cm的长方形区域。第三部分为-5cm15cm的长方形区域。min Q-Q+。27=：+Qi=%+&+%5左=ZX-+ZZXk=1,2,3i=l i=l j=2Qi=1,2,32噜4二18C23 vi=l Vt3 tQn每个区域的刀片转动的顺序还是d-e-f-g-h-a-b-c-f,我们用牺牲刀具的 转动时间来做到减短钻头所行总路线，下面是我们针对每个区域所求的时间和 所行的最短径。表三：第一区域路程及时间刀具所需大的 孔点最短路程(所有 孔点及不同孔点 之间的和)(cm)转换下一 刀具的路 程(cm)路程之和(cm)时间(s)打的 孔数(个)dGD56.26056.263.12101eDI46.966.1453.12.9591fJ29.2110.9140.122.2210gGF8.840.359.190.51120hFH12.9211.7524.671.376aAC40.461.1241.582.3155bB65.704.4170.113.89167cCUE49.861.0650.922.8377d.0000e0000fEG21.083.9825.061.3927合 计：.371.0120.59654表四：第二区域路程及时间刀具所需大的 孔点最短路程（所有 孔点及不同孔点 之间的和）（cm）转换下一 刀具的路 程（cm）路程之和（cm）时间（S）打的 孔数（个）dGD50.74050.742.8254eDI50.7410.0160.753.3754fJ42.0010.1652.162.8914gGF6.3613.4619.821.1010hFH30.283.0033.281.8514aAC189.8111.04200.8511.16838bB188.571.34189.9110.55588cCUE127.975.49133.467.41259d.0000e0000fEG48.8811.6960.573.3659合 计：.801.5444.511890表五：第三区域的路程及时间刀具所需大的 孔点最短路程(所有 孔点及不同孔点 之间的和)(cm)转换下一 刀具的路 程(cm)路程之和(cm)时间(s)打的 孔数(个)dGD30.245.7339.972.2277eDI39.497.5847.079.3477fJ23.013.5426.552.625gGF17.983.3821.361.1924hFH14.366.3420.801.1620aAC32.565.3837.942.1137bB16.615.3421.951.2132cCIJE56.487.0063.483.5368d.0000e0000fEG24.29024.291.3529合 计：.303.4124.73369结果：tl=18*10*3=540st2=20.59+44.51+24.73=89.83st3=(654+1890+369)*0.5=1456.5sT=tl+t2+t3=2086.33sS=371.01+801.54+303.41=1475.96 cmQ=006*10*147596+3*(10*18)760*7=948.58(元)问题二：(一)模型的分析与建立：由于是双钻头的打孔机，且作业是独立的，但为避免钻头间的触碰和干 扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm,因此我们采取了 分区域的做法，即两个钻头分开作业，这样能够很好地避免钻头间的触碰和干 扰。根据分析，决定将其分为四个区域，设两个钻头为钻头A和钻头B,钻 头A行走区域一(x-5)和区域二(5x0),钻头B行走区域三(0 x5),当钻头A走区域一时，钻头B走区域三，并根据各个区域各种 孔型分布特点，得出各个区域刀具转换形式，见下列各表：区域一、三、四的刀具转换方式:区域二的刀具转换方式:目标函数：min Q=P2fl+P1SS=s即+sk2.=max（q）Tk+t.nk k vT=max（，）（二）模型的求解：同样地运用类似最小生成树的方法，用java设计程序（见附录3）,求 得各个区域钻头A,B行走各种孔型最短路径的各个端点坐标及路程，结果见 下列各表：表六：区域一（x-5）钻头A所走的路程及时间刀具所需大的 孔点最短路程（所有 孔点及不同孔点 之间的和）（cm）转换下一 刀具的路 程（cm）路程之和（cm）时间（S）打的 孔数（个）dGD48.27048.272.68101eDI40.978.0048.972.7291fJ29.218.3437.552.0910gGF9.6409.640.5420hFH12.930.8713.800.776aAC34.464.4138.872.1655bB55.7010.4065.103.62167cCUE40.47040.472.2571d.0000e0000fEG21.08021.081.1727合 计：.323.7518.00548表七：区域二（-5x0）钻头A所走的路程及时间刀具所需大的 孔点最短路程（所有 孔点及不同孔点 之间的和）（cm）转换下一 刀具的路 程（cm）路程之和（cm）时间（S）打的 孔数（个）fJ18.926.2625.181.403g00000hH09.769.760.541aAC89.088.0797.155.40424bB96.052.7298.775.49336cJIEC41.992.4054.393.0299dD12.87012.870.7119eD12.874.0616.840.9419fE20.99020.991.1616合计：.335.9518.66917表八：区域三（0 x5）钻头B所走的路程及时间刀具所需大的 孔点最短路程（所有 孔点及不同孔点 之间的和）（cm）转换下一 刀具的路 程（cm）路程之和（cm）时间（S）打的 孔数（个）dGD42.06042.062.3419eDI40.611.2441.852.3218/fJ25.305.9731.271.748gGF22.70022.701.2631hFH6.300.737.030.3929aAC26.265.7331.991.78276bB50.844.9155.753.10154cCIJE63.21063.213.51117d.0000e.0000fEG27.13027.131.5147合计：.322.9917.95699tl=18*10*3+18*8=684s；t2=23.66+18.66=42.32s；t3=(699+917)*0.5=808s；T=tl+t2+t3=1534.32sS=323.75+335.95+425.17+322.99=1407.86 cmQ=0.06*10*1407.86+(10*18*3+18*8)760*7=924.516(元)6.模型评价与推广 优点：由于打孔的数量太多,如果以传统的遗传算法或者是蚂蚁算法去求解问题，这将会花费非常多的时间在计算孔点的距离。通过我们自行设计的 快速算法，可以在较短时间内得到孔点间相对较优的路程。另外，通过 分析刀具转换方式与孔点的关系，我们设计的刀具转换方式也大大缩小 了加工钢板的时间，这对于加工厂来说，就能过大大地提高产量。缺点：虽然我们缩短了计算孔点之间的距离，但由于我们算法也存在一定的缺陷，所以在获得最短路程上，我们可能得不到最短的路径，导致加工钢 板的成本会比较高。参考文献：刘焕彬库在强，数学模型与实验，北京：科学出版社，2008姜启源，谢金星等，数学模型，北京：高等教育出版社，20113肖华勇，数学建模竞赛优秀论文一一精选与点评，西北工业大学出版社，20074 Fred Buckley等（著），李慧霸等（译）图论简明教程，清华大学出版社，20055韩明等，数学实验，同济大学出版社，2009附录一（孔点分布图）：孔点分布图：ABCDEFGH I J T T M-I wt 7 r H4 7 F U-I 7 F U 4 7 r U-l 7 T U-I wt ffd ffd OMd ffuj ffd ffuu Cyd ffd 74Ju才-44JU44JU，“JUJu“JU4/1Ju4/JU7,川FD(Eu)x(cm)XrD附录二（程序）：（一）：public class T public T()/TODO Auto-generated constructor stub)public String rowl()return n./bin/three/AC 1.txtn;)public String row2()return n./bin/three/AC2.txtn;)void min()int pl=new Zh().read(new T().rowl();读取文件 我们要的是个 数int p2=new Zh().read(new T().row2();/读取文件 我们要的是个 数int p=new intpl.length;储存位置(多少点)的数组/int q=new intpl.length;for(int i=0;ipl.length;i+)(pi=i+l；/qi=i+l；)/*规划坐标的位置(点数)例：第五个坐标我们设为5*/int k=new int2;定义储存在运行的点的数组int dox=0;表示被定义为无效点的个数double sum=0;路程值intml=0,m2=0,m=0;临时值，储存临时的停置double w=new Zh().row();获得两点之间的距离for(int i=0;ipl.length;i+)for(int j=0;j p 1.lengthy+)if(wij=0)wi用=99999999999.9999999;/设为无穷大)/*将无效距离(既自己与自己的距离设为无穷大)*/System.out.println(wi);double min=w00;/设一开始的最短距离为无穷大for(int i=0;ipl.length;i+)for(int j=0;j p 1.length;j+)(if(wijmin)(min=wij;k0=i;kl=j；)/*在存有众多距离的数组中找出最短距离，作为开始*/sum=sum+min;/System,out.println(sum);while(doxp 1.length-2)(for(int i=O;ip.length;i+)if(pi!=O)(m=pi;break;)/*找出运行到还有效的位置；无效为0*/min=wk0m-l;ml=k0;m2=m-l;/*设循环这一次最初的最小距离min；*临时的ml和m2位置(既它有可能成为k数组的值)*/for(int j=0;j p.length;j+)(if(pj!=O)排除为0的无效位置(if(pj-l)!=kl&wkOpj-lmin)排除 路线会围成一圈(min=wk0pj-l;ml=k0;m2=pj-l;*得到临时的min值和它的位置;*/)if(p-l)!=kO&wklpj-lmin)排除 路线会围成一圈(min=wklpj-l;ml=kl;m2=pj-l;/*得到临时的min值和它的位置；*/)sum+=min;当前路程 if(ml=kO)(d0 x+;无效位置个数循环一次加一pkO=O;无效位置设为0 k0=m2;替换被围绕运行的位置)else(dox+;无效位置个数循环一次加一pkl=O;无效位置设为0kl=m2;替换被围绕运行的位置)for(int i=O;ip.length;i+)if(pi!=O)System.out.println(plpi-l*0.0000254+n+p2pi-l*0.0000254);/*得到最后还有效的两个位置，确定起点和终点*/System.out.println(sum*0.0000254);)/*param args*/public static void main(String args)/TODO Auto-generated method stub new T().min();)(二)：import java.io.BufferedReader;import java.io.FileReader;public class Zh/*/public Zh()/TODO Auto-generated constructor stub)public int read(String s)BufferedReader dos=null;StringBuffer s2=new StringBuffer(nn);try(dos=new BufferedReader(new FileReader(s);String fos=null;s2.append(dos.readLine();while(fos=dos.readLine()!=null)s2.append(n H+fos);/System.out.print(s2);)catch(Exception e)e.printStackTrace();finallytry(dos.closeQ;)catch(Exception e)e.printStackTrace();)String s3=s2.toString().split(n n);int s4=new ints3.length;for(int i=0;is3.1ength;i+)s4 i=Integer.parseInt(s3 i);return s4;)public double row()Zh zh=new Zh();int pl=zh.read(new T().rowl();int p2=zh.read(new T().row2();int p=new intpl.length;int q=new intpl.length;doublet w=new double pl.length p2.length;for(int i=0;ipl.length;i+)(pi=i+l；qi=i+l；)for(int i=O;ipl.length;i+)for(int j=0;j p2.length;j+)(wij=Math.sqrt(Math.pow(pli-plj),2)+Math.pow(p2i-p2j),2);)return w;)/*param args*/public static void main(String args)/TODO Auto-generated method stubnew Zh().row();)(三)：public class Xz public static void main(String args)/TODO Auto-generated method stub int pl=new Zh().read(new T().rowl();int p2=new Zh().read(new T().row2();StringBuffer s=new StringBuffer(nn);for(int i=O;ip 1.length;i+)if(pli-196850)(s.append(i+n:n);System.out.print(pli+n n);)System,out.println();String p3=s.toString().split(n:n);for(int i=0;ip3.1ength;i+)System.out.print(p2Integer.parselnt(p3i)+n);)(四)：public class Xz2 public static void main(String args)/TODO Auto-generated method stubint pl=new Zh().read(./bin/shuju/C 1.txt);int p2=new Zh().read(n./bin/shuju/C2.txtH);StringBuffer s=new StringBuffer(nn);for(int i=0;ipl.length;i+)if(-19685Opli)s.append(i+H:n);String p3=s.toString().split(n:n);for(int i=0;ip3.1ength;i+)if(p2 Integer.parselnt(p3 i)590551)System.out.print(pl Integer.parselnt(p3i)+)；System,out.println();for(int j=O;jp3.1ength;j+)if(p2 Integer.parselnt(p3 j)590551)System.out.print(p2lnteger.parselnt(p3j)+n);)(五)：public class Hz3 public static void main(String args)/TODO Auto-generated method stubint pl=new Zh().read(./bin/shuju/J 1.txt);int p2=new Zh().read(n./bin/shuju/J2.txtn);StringBuffer s=new StringBuffer(,n);for(int i=O;ipl.length;i+)if(-196850pli)s.append(i+”:)；String p3=s.toString().split(n:)；for(int i=0;i590551)System.out.print(pllnteger.parselnt(p3i)+n);System.out.println();for(int j=0;j 590551)System,out.print(p2 Integer.parselnt(p3)+”)；)论文二:打孔机生产效能的提高摘要过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制 板费用的30%到40%,打孔机主要用于在制造印刷线路板流程中的打孔作业。因此提高打孔机 的生产效能是降低印刷线路板成本的最主要途径。本文通过实现刀具转换最优顺序的前提下，运用蚁群算法找到最优线路，及最短距离。使行进成本和刀具转换成本均达到最低，以此减少 打孔机总打孔成本。问题一：单钻头进行作业时，首先根据钻头上各个刀具的分布，结合各孔型对刀具的具体 要求，经过分析找到了刀具转换次数最少并能完成各孔型对刀具加工次序特殊要求的换刀顺 序：d-c-b-a-h-g-f-e-co然后运用蚁群算法，在整个区域内分别计算出十种孔型的最优路线和 最短路径，再分别计算行进时间，及作业成本。然后与刀具转换时间和成本及两孔型之间钻头 移动时间和成本进行汇总分析，所得最后数值则为所求。其具体对过孔加工顺序按蚁群算法得 出的加工顺序进行。问题二：双钻头作业时，由于两个钻头独立工作，两个钻头可以同时进行打孔，也可以一 个钻头打孔，另一个钻头行进或转换刀具。但为了避免钻头间的触碰和干扰，在过孔加工的任 何时刻必须保持两钻头间距不小于3cm,为保证这一要求本文将整个电路板按过孔分布的密集 程度划分为四个区域，首先让两个钻头在一、四两个对角线区域内单独工作，加工完毕后在分 别转向三、二两个区域。换刀方案保持不变，仍然利用蚁群算法找出各个区域内的最优路径和 最短路线，再分别计算出行进时间，行进成本。最后将四个区域的总时间、总成本进行汇总得 出结果即为问题二的结果。其具体对过孔加工顺序一就按蚁群算法对个区域所得出的加工顺序 进行。将问题一的结果与问题二的行进成本、换刀成本、行进时间、换刀总时间进行比较分 析，计算出生产效能不同。同时结合问题一、问题二的结果分析打孔机的两钻头合作间距对作 业路线和生产效能产生的影响。最后根据遗传算法对整个计算进行检验、分析及总结。关键字：最优刀具转换蚁群算法遗传算法生产效能提高一、问题的提出及研究意义1.1问题背景过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制 板费用的30%到40%,打孔机主要用于在制造印刷线路板流程中的打孔作业。一般打孔机上有 8种刀具，a,b,c,d,e,f,g,h,依次排列呈圆环状，如图1所示：h co og dy e图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使 用另一种刀具。相邻两刀具的转换时间是18 s,例如，由刀具a转换到刀具b所用的时间是 18s,其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换 到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具鼠将任一刀具转换 至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c,所需的时间 是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180mm/s,行 进成本为0.06元/mm,刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具 转换，但相应费用不减。而孔的类型对刀具具有一定的要求，不同的刀具加工不同的孔型，有的孔型只需一种刀具 来完成，有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c,且 加工次序为a,c。表1列出了 10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加 工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要 求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证 所需刀具加工次序正确即可为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两 钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两 钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。1.2 需要解决的问题1.2.1 单钻头作业给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作 业成本。1.2.2 针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并 与传统单钻头打孔机进行比较，其生产效能提高多少。1.2.3 研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。1.3 研究意义过孔的加工费用通常占制板费用的30%至U 40%o提高打孔机的生产效能对降低印刷线路板 成本起着至关重要的作用。二、问题分析打孔机的生产效能主要取决于以下几方面：(1)单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型 钻孔作业时间都是相同的。(2)打孔机在加工作业时，钻头的行进时间。(3)针对不同孔型加工作业时，刀具的转换时间。问题一分析：本题要求提高打孔机在传统单钻头作业时的工作效能，即降低刀具转换成本 和钻头行进成本。由于不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，有的孔型 需要多种刀具及规定的加工次序来完成，本题中有8种刀具，相比较于孔的两千多坐标来说，确定刀具的转换顺序比较简单，所以应先确定刀具的最短转换顺序，再运用模型计算出最有路 径和最短路线。打孔机是打完一个电板之后再按照原来的最优线路进行下一个电板，所以在打 完一个电板的最后一个点之后，钻头应回到起始点，对于每种刀具而言，每个孔型的每个坐标 只需加工一次，然后返回到出发点即可。根据以上分析，该问题与旅行商问题相似，可以采用 蚁群算法、遗传算法和模拟退火算法进行求解。由于本题的数据比较小，而蚁群算法又具有局 部搜索速度快、收敛性良好的优点，所以本文采用蚁群算法对本问题的最优线路和最短路径进 行求解，用遗传算法对蚁群算法进行优化和检验。问题二分析：在双钻头作业时，两个钻头独立工作，且为避免钻头间的触碰和干扰，在过 孔加工的任何时刻必须保持两钻头间距不小于3cm,所以考虑将一块电路板根据孔的密集程度 划分出四个不同的区域：一区(xv0,y4xl()5),二区(x0,y4xl()5),三区(x0,y0,yv4xl()5)(单位：l/100mil)。如图四。第一个钻头工作路线为先 打一区再换到三区工作，第二个钻头先打四区再打二区，使两个钻头的距离始终保持大于等于 3cm。每个区域的刀具转换顺序与问题一相同，一就运用蚁群算法分别计算出各个区域的最短 路线和最优路径，再根据已知的钻头行进速度180mm/s和换刀时间计算出总的时间及成本。三、模型的基本假设1、单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假设对于同一孔 型钻孔作业时间都是相同的。2、在计算两孔之间距离时，为了简化问题，这里假设打孔机的钻头看作一个质点。3、为了计算行进费用，需要计算行进时间，为了简化问题，这里假设打孔机的行进是一个 匀速运动。四、符号