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

打孔机生产效能的提高摘要本文研究单钻头作业的最优作业线路以及刀具转换最佳顺序，运用蚁群模型以及最优化模型的方法找到最佳换刀顺序，提高了某类打孔机的生产效能。模型一：针对问题一，建立蚁群模型，在完成一个电路板的过孔加工时，钻头行进时间和刀具转换总时间越短，生产效益越高。钻头行进总时间由钻头进行路线决定，而刀具转换时间由线路板上由各孔的位置以及钻头行进方案决定。在此过程中，只要考虑钻头行进时间以及刀具转换时间两个过程即可。考虑最先使用的刀具与最后使用的重合以及尽量使刀具转化次数达到最小值。得到以下刀具转换方式最优解:d-c-b-a-h-g-f-e-d-c-d，根据刀具的转换方式可知，我们需要加工孔型的次序为：DGEBACFHFGEGDICIJ。通过matlab2010进行拟合，得到各刀具的最佳行进路线（结果见表一至七），刀具转换成本为18.9元。模型二： 针对问题二，建立最优化模型。 当打孔机设计成双钻头时，由于作业时各钻头相互独立，为了解决双钻头最优作业方案，为避免钻头间的触碰和干扰，我们采取了分区域的方法，即两个钻头分开作业。我们将所有孔型的孔点显示在同一个图像中（图11），并将其均分为四个区域，使一个转头工作在区域一、三，同时另一个转头工作在区域二、四。使用matlab2010编程后得区域一刀区域二的最短路线为10000，区域三到区域四的最短路线为22047（结果见表八至表十一），此外得到此情况下刀具装换成本为75.6元。双钻头最优加工路径与单钻头的最优加工路径相比，在不同钻孔速度下使用双钻头同时加工的新算法能节省加工时间，有效提高了打孔机的加工质量、加工效率、生产效能。关键词：蚁群模型 最短路径 最优化模型 一、 问题重述1.1问题背景过孔是印刷线路板的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。打孔机的生产效能主要取决于单个过孔的钻孔作业时间、钻头的行进时间、以及刀具的转换时间。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，如图1所示。图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。1.2需要解决的问题（1）单钻头作业的最优作业线路、行进时间和作业成本。（2）给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较。（3）究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、 问题分析1、问题1：根据题目我们可以得出：打孔机工作时间=钻头行进时间+刀具转换时间+钻孔时间。但是对于同一孔型，钻孔时间相同，此时只要考虑钻头行进时间以及刀具转换时间两个过程即可，在此问题中我们只要考虑以上两个因素的总时间最短。在此钻头行进和刀具转换是相互独立的，要使总时间最短，即钻头行进时间和刀具转换时间分别是最短的。根据以上分析，我们可以得到一个关系式：总时间=钻头行进时间+刀具转换时间。行进成本为：总路程*0.06元/mm刀具转换的时间成本=刀具转换时间*7元/分在工作过程中，我们需要首先确定刀具的转换方向，这里需要考虑两点：（1）由于一块板加工完毕后需要加工下一块板，而且连两块板的加工方式是一样的，那么刀具在最后必须转换回第一次用的刀具；（2）刀具转化次数达到最小值。我们可以很容易得出结论，第一次使用的刀具必定不需要转换便可以直接运用到加工过程，否则会增加刀具转换的时间。除此之外，我们还要尽可能一次使用同一种刀具不进行更换，以避免过多更换刀具浪费不必要的时间。除了要确定刀具转换时间外，我们还需要确定钻头的最佳行进路线。此外，根据附件给出的信息，我们按照孔型（AJ）过孔中心坐标的数据，应用matlab2010画出各孔型在xy平面的散点图。A、B、C类型的孔数目多，且排列较为杂乱，给处理数据带来一定的困难，以A类型为例进行分析。 图2孔型A各孔分布我们注意到孔型的各孔主要集中分布在下半部分，则刀具主要在此部分运动，且孔分布不对称间隔无规律，刀具行走的路径情况很多，处理起来需要一定的时间。D、E、F类型的孔数目相对较多，但是排列有一定的规律，根据排列规律找到方法较容易，以D类型为例进行分析。图3孔型D各孔分布我们注意到孔型的各孔在整个平面分布较为匀称，则，刀具需要运动范围较广，且孔分布有一定规律，则钻头的路径也会遵循一定规律。同时，由于孔需要两种刀具进行加工，因此要注意刀具在同一个孔工作的顺序。G、H、I类型的孔排列规律不是很明显，但是孔数目少，数据处理起来较为容易。（如下图所示）图孔型I各孔分布我们注意到孔型的各孔在整个平面分布较为匀称，则，刀具需要运动范围较广，但是孔的数量十分少，则钻头行走的路径情况列举出来也不多。同时，由于孔需要两种刀具进行加工，因此要注意刀具在同一个孔工作的顺序。J类型的孔排列规律不是很明显，但是孔数目相对少，数据处理起来相对容易。（如下图所示）图孔型各孔分布我们注意到孔型的各孔在整个平面分布较为匀称，则，刀具需要运动范围较广，但是孔的数量规律性不强，孔的数量不多，则钻头行走的路径情况列举出来也不多。同时，由于孔需要两种刀具进行加工，因此要注意刀具在同一个孔工作的顺序。可利用分析单钻头的行进时间和作业成本方法得出双钻头的在最优作业路线条件下的行进时间和作业成本并与传统单钻头打孔机进行比较，可知其生产效能提高了多少。2、问题二：印刷线路板过孔中心坐标的数据与问题一一样，不同的是，本题是双钻头的打孔机（每个钻头的形状与单钻头相同），当打孔机设计成双钻头时，由于作业时各钻头相互独立，且有合作间距的限制，因此在解决双钻头最优作业方案时，我们在单钻头作业的基础上再加上另一个钻头作业所需的各种费用并增加约束条件，保证合作间距在要求范围之内。此钻孔机作业是独立的，但为避免钻头间的触碰和干扰，在过孔加工的任何时间必须保持两钻头间距不小于3cm。基于这两个条件，我们采取了分区域的做法，即两个钻头分开作业，这样就能够很好地避免钻头间的触碰和干扰。由点的分布图分析，最终平均分成四块区域，按照区域分布特点，确定刀具转换方式与各种孔型之间的打孔顺序。按照问题一的方法依次求出各个区域最短行进路程，加总即为最路程。三、 模型的基本假设1、 机器在工作期间不会因为操作原因、环境等因素损坏；2、 附件中所给出的坐标数据均有效，无效的坐标可忽略；3、 钻头行进和刀具转换两个过程是相互独立的；4、 刀具顺时针转换以及刀具逆时针转换时间完全相同；5、 过孔的钻孔作业时间，是由生产工艺决定的，这里可以假设对于同一孔型钻孔作业时间都是相同的；6、 在计算两孔之间距离时，假设打孔机的钻头看作一个质点； 7、 打孔机的行进过程是一个匀速运动。四、 符号定义和说明编号符号符号具体含义1M代表蚂蚁数量2N代表城市数量3i代表第i只蚂蚁4j代表第j座城市5x代表迭代次数，此数大于能够得出最优解得迭代次数6代表边（i，j）上的信息素浓度7代表启发信息，d是过孔中心i和j之间的距离8代表蚂蚁k已经访问过的过孔中心列表9和反映了信息素与启发信息的相对重要性；五、 模型建立与求解5.1模型一的建立与求解根据题目我们可以得出：打孔机工作时间=钻头行进时间+刀具转换时间+钻孔时间。但是对于同一孔型，钻孔时间相同，此时只要考虑钻头行进时间以及刀具转换时间两个过程即可，在此问题中我们只要考虑以上两个因素的总时间最短。在此钻头行进和刀具转换是相互独立的，要使总时间最短，即钻头行进时间和刀具转换时间分别是最短的。根据以上分析，我们可以得到一个关系式：总时间=钻头行进时间+刀具转换时间。5.1.1模型背景蚁群算法是意大利学者Dorigo等人于1991年创立的，是继神经网络、遗传算法、免疫算法之后的又一种新兴的启发式搜索算法。蚂蚁在外出觅食的过程中,不断地在经过的路径上释放信息激素以便和其他的蚂蚁进行联系，这种信息激素的浓度随着经过该路径的蚂蚁数量而增大，而蚂蚁在回巢或觅食时也会选择信息激素浓度较大的路径，这就会有更多的蚂蚁选择此路径，这就是一种正反馈现象。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的概率就越大。5.12模型的建立根据以上分析，我们可以得到一个关系式：总时间=钻头行进时间+刀具转换时间。在工作过程中，我们需要首先确定刀具的转换方向，这里需要考虑两点：（1）由于一块板加工完毕后需要加工下一块板，而且连两块板的加工方式是一样的，那么刀具在最后必须转换回第一次用的刀具；（2）刀具转化次数达到最小值。根据以上的考虑方式，得到以下最优解:d-c-b-a-h-g-f-e-d-c-d我们可以很容易得出结论，第一次使用的刀具必定不需要转换便可以直接运用到加工过程，否则会增加刀具转换的时间。除此之外，我们还要尽可能一次使用同一种刀具不进行更换，以避免过多更换刀具浪费不必要的时间。除了要确定刀具转换时间外，我们还需要确定钻头的最佳行进路线。根据刀具的转换方式可知，我们需要加工的次序为：DGEBACFHFGEGDICIJ研究表明,蚂蚁具有找到蚁巢与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失)来实现的。蚂蚁在一条路上前进时，会留下挥发性信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.。对于一条路径,选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈。通过这种正反馈，蚂蚁最终可以发现最短路径。首先将m只蚂蚁随机放置在n个过孔中心（过孔中心可视为蚂蚁的食物所在处），位于过孔中心i的第k只蚂蚁选择下一个过孔中心j的概率为: 其中： 表示边（i，j）上的信息素浓度； 是启发信息，d是过孔中心i和j之间的距离；和反映了信息素与启发信息的相对重要性； 表示蚂蚁k已经访问过的过孔中心列表。 当所有蚂蚁完成周游后，按以下公式进行信息素更新其中：为小于1的常数，表示信息的持久性。 其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。步骤：1.初始化：随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中;2.迭代过程（流程图如下）执行公式（1）j=j+1imjn-1i=i+1k=k+1执行公式（2）计算每只蚂蚁所经过路途的长度开始k=1;i=1;j=1kx输出结果结束NYYNY5.1.4模型的求解如问题分析中所示，由于点的个数太多，因此应用matlab画出所有孔型的点显示在一个界面上，如下图所示：图所有孔型分布散点图 应该matlab2010将各刀具具体数值带入蚁群模型中进行计算，运行后得到以下结果：（由于情形较多，此处以c、d刀为例）图、d刀最短路径优化结果 图、d刀平均路径与最短路径图、c刀具最短路径优化结果 图、c刀平均路径与最短路径 说明1、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。2、终止条件 （1） 给定一个外循环的最大数目；（2） 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。最终得到各刀具行进路线为：表一d刀行进路线193198196195197191194190192117118343536132131104391718871562121413111519201629303120120220420921021121220720620511311211511617217117016916816716616517317417517617717817918015615513914013813713613513413314915015115215315422021822622421621422222721921322122321521722522812612712812913011425211811861871881891851841831821081091101111221211201191571411421431441451461471481641631621611601591581992002292302312321231071068910588104871038610285101841008399829881978096799578947793769275917457404158425943604461456246634764486549665067516852695370547155725673903332371251242082032627282423223839最短路径：5900000表二c刀行进路线7374451514232528293231465253545556504948477118981772754566767880828486888991909294959387858381797720101921246322712234111596557606164635813165143414035363738424433267068623027396769最短路径：3.88E+06表三h刀行进路线26343332252730312928353640391516812201795131461018222124231911738373142最短路径：3104500表四g刀具路线504834240384613644494354345239473741322527303129282634331911715168122024211795131461018225152535423最短路径：3.27E+06表五f刀行进路线148149141451514231421452928146144143253231465253545556504948471501517118981772754566154155767779818385878991939594929088868482807820103137133125121129112819212461113112312713513212412034575965616463581313016511221261341381392136221121271131141156038373635404142431531524433267010110911811110399105110119961041061171001089810297107116686230273973746967147140最短路径：3200000表六e刀行进路线829881644865496650675168526953705471557256739010689105881048710386102851018410083999780967995789477937692759174574041584259436044614562466347323319920014816416314714614514414314214115715815916016116211111010910811912012112218518418318218118618718818913012912812712611425212202222122112102092042052062072192212141161131121152131721711701691681671661651731741751761771781791801561551541381391401371361351341331491501511521532012023130291615192014121113562178181734109131132363534117118191194190192193198196195197208203262728242322383912412537215217218123216107最短路径：5.92E+06表七c刀行进路线272818171651582891552342012172313052181091061012612592572552562582602622642662682702692672652631078688108110138694121521222518530019119719218629718218719426192219306202220232991031041051021001612921621682372033072212332221832981881951894753205302206208207282281286285280278434435342772792722716867703024723924024124224324424524625425325225125024924824162013190299184193196199301198200204151145143144146152142136132128124120116112111115119123127131135141147149154114113117121125129133139140134130126122118153137138150148238293163169164210214216304213283284287929693288828777736961463633179294170173174117510175295171176180323750545552648184858079839490917875764948424541403938293123166290156235157159291160167236971417729617217818127359656656606263572742233082292262252762752303092272242289895892123032152112097472715851最短路径：8.68E+06由于行进成本=总路程*0.06元/mm；刀具转换的时间成本=刀具转换时间*7元/分 计算得出行进成本为18.9元。5.1.5算法的缺点：1）收敛速度慢2）易于陷入局部最优3）随着城市数目的增多,问题空间将呈指数级增长。因此在处理大量数据的时候，会显得非常慢。5.2模型二的建立与求解在打孔过程中，一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。5.2.1模型建立我们将所有孔的分布情况展现在一个图中，将其平均分为四个部分。（如下图所示）为了确保钻头在行进过程中不相互触碰，我们假设一、二号钻头分别在区域一、三上完成打孔后再分别进入到区域二、四运行。 图11竖向划分区域 图12横向划分区域图11与图12同样是平均分区域，但是横向划分区域所行走的直线比纵向划分区域要长，因此行进时间以及费用都会增加，因此我们选择图11方案。根据图11，为了确保钻头在行进过程中不相互触碰，我们假设一、二号钻头分别在区域一、三上完成打孔后再分别进入到区域二、四运行。由于已经确定了刀的顺序，那么我们需要找出区域一中和区域二中用d刀加工相距最小的两点。当然，在区域三和区域四用也应该用同样的办法找出这两点。这样才可以保证刀具在行进过程中所走过的路程最短。 （4）其中，在钻头一中，（x2，y2)表示区域2的孔的坐标，（x1,y1）表示区域1的孔的坐标；钻头二中，（x4，y4)表示区域4的孔的坐标，（x3,y3）表示区域3的孔的坐标5.2.2模型求解结果如下表八、区域一区域一刀具dcbah最短路线29440001885500618140054887001018000刀具gfedc最短路线3748202518700265240003912500表九、区域二区域二刀具dcbah最短路线119600156840018591002235900767910刀具gfedc最短路线260400156840011960001776900表十 、区域三区域三刀具dcbah最短路线27704002424000348850040877001964900刀具gfedc最短路线23378002551600276390002893700表十一、区域四区域四刀具dcbah最短路线196060010236014029000121968刀具gfedc最短路线0102360247690002468100表中数据显示了不同刀具分别在四个区域中的最短路线。用matlab编程计算，编程后得区域一刀区域二的最短路线为10000，区域三到区域四的最短路线为22047。（具体程序看附件3）由于行进成本=总路程*0.06元/mm；刀具转换的时间成本=刀具转换时间*7元/分 计算得出行进成本为18.9元。参考文献：1韩中庚.数学建模方法及其应用，北京：高等教育出版社，2005. 2 姜启源,谢金星,叶俊.数学模型M.北京:.2003年8月第三版3周明，孙树栋. 遗传算法原理及应用，北京：国防工业出版社，1999.4 段海滨.蚁群算法原理及其应用M.北京：科学出版社，2005附：1、画出各孔型在xy平面的散点图程序（以H孔型为例）x=;y=;plot(x,y,b*);title(孔型H过孔中心坐标);xlabel(x值);ylabel(y值);2、求最佳路径的程序（以H孔型为例）%蚁群算法求解TSP问题的matlab程序 clear all close all clc %初始化蚁群 m=5;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解 C=;%城市的坐标矩阵 Nc_max=80;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m） alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象 beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度 rho=0.5;%0rho1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数 Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大 %变量初始化 n=size(C,1);%表示TSP问题的规模，亦即城市的数量 D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离 for i=1:n for j=1:n if ij D(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2); end D(j,i)=D(i,j); end end eta=1./D;%启发式因子，这里设为城市之间距离的倒数 pheromone=ones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1 tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度 Nc=0;%循环次数计数器 routh_best=zeros(Nc_max,n);%各次循环的最短路径 length_best=ones(Nc_max,1);%各次循环最短路径的长度 length_average=ones(Nc_max,1);%各次循环所有路径的平均长度 while Ncq0 for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; position=find(probability=max(probability); to_visit=city_remained(position(1); end else for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; end probability=probability/sum(probability); pcum=cumsum(probability); select=find(pcum=rand); to_visit=city_remained(select(1); end tabu_list(i,j)=to_visit; %* end end if Nc0 tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失 end %记录本次循环的最佳路线 total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径 for j=1:(n-1) total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度 end total_length(i)=total_length(i)+D(r(1),r(n);%最终得到第i只蚂蚁在本次循环中所走过的路径长度 end length_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度 position=find(total_length=length_best(Nc+1);%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的 routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径 length_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度 Nc=Nc+1 %更新信息素 delta_pheromone=zeros(n,n); for i=1:m for j=1:(n-1) delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)+Q/total_length(i);%total_len