毕业设计（论文）-基于提高打孔机生产效能的数学模型.docx

摘 要过孔是印刷线路板的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%。打孔机主要用于在制造印刷线路板流程中的打孔作业，通过对加工过孔的最优作业路线设置的讨论，可以提高打孔机的生产效能。以下分别给出了单钻头作业和双钻头作业的最优作业线路。问题一要求给出单钻头作业的最优作业线路、行进时间和作业费用，属于广义的旅行商问题（tsp问题），将其转化为典型的旅行商问题。通过构建单钻头作业时刀具转换方式的判断函数a，可以得到单钻头作业的刀具转换费用w1，及刀具转换费用w2。将w1+w2作为元素，构建基于tsp问题的等效赋权图。这样可以很好地将广义的旅行商问题转化为典型的旅行商问题。应用蚁群算法对模型进行编译，得到单钻头作业的最优加工线路，行进时间为83.4s，作业费用为993.15元。对于问题二，从单钻头改为了双钻头作业，属于多旅行商问题（mtsp）。同时，增加了两钻头的合作间距不小于3cm这一限制。基于对单钻头作业路线的求解，建立了区域模型，将整个印刷线路板主要分为四个区域，使每个区域的的单孔数目大致相等，在板子中心位置留出一个半径为32/2cm的中心圆域，用来控制两钻头的合作间距。将两个钻头分别按照单钻头加工的最优作业路线，依次加工板子的左半区域和右半区域，先完成的钻头转而加工中心圆域，由此达到使双钻头作业的最优化加工线路。求得双钻头加工的最优线路下的钻头行进时间为63.23148s，作业费用为785.8元。通过计算，采用双钻头作业时作业时间相较于传统的单钻头作业减少了24.2%。加工费用降低了20.87%，在节省加工时间的同时，减少了加工费用有效提高了打孔机的加工质量，加工效率和生产效能。为了研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。我们改变中心圆域的半径为2cm，得到该限制条件下的钻头行进时间为63.19s，加工总费用为779.2元。说明减小打孔机的两钻头合作间距生产效能明显提高。综上，本文得出了打孔机单钻头和双钻头作业的最优线路。关键词：tsp 等效赋权矩阵 蚁群算法 区域模型目 录一.问题重述1二.问题的分析1三.模型的假设及符号的说明23.1.模型的假设23.2.符号说明3四.模型的建立与求解34.1.单钻头模型34.1.1 刀具转换费用44.1.2.钻头行进费用54.1.3.优化模型54.1.4.基于tsp问题的等效赋权图64.1.5.模型的求解74.2.双钻头模型94.2.1.双钻头加工的区域模型104.2.1.区域模型的优化114.2.2.模型的求解134.2.3.对改变双钻头合作间距的研究16五.模型的评价及改进175.1.优点175.2.改进18参考文献19一.问题重述本问题旨在提高某类打孔机的生产效能。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，而且8种刀具的顺序固定，不能调换。相邻两刀具的转换时间是18 s。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进费用为0.06元/mm，刀具转换的时间费用为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型。一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，要保证所需刀具加工次序正确即可。请建立相应的数学模型，并完成以下问题：（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业费用。（2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业费用，并与传统单钻头打孔机进行比较，其生产效能提高多少？（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二.问题的分析本问题旨在提高某类打孔机的生产效能。所谓生产效能，即单位时间内的生产能力、加工效率。欲有效地提高打孔机的生产效能，可以通过缩短钻头的加工路径长度，来在减少加工时间的基础上减少加工费用。孔群的加工路径优化问题可以抽象为典型的旅行商问题（tsp），钻头可表示成是旅行商，这样可以将求钻头的最短路径问题转化为了求旅行商的问题。对于问题一，本问题属于双目标优化问题。要求给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业费用。优化目标为使加工时间和作业费用最优的作业线路。考虑到总的作业费用主要包括刀具的转换费用和钻头的行进费用，我们需要分别建立模型对刀具的转换费用w1和钻头的行进费用w2进行计算。其中行进费用w2的计算可以用解决tsp问题的方法，借助蚁群算法进行近似优化计算。然后建立优化模型，以w1和w2加和求得加工孔时的最小加工费用作为元素，并利用类似于求解tsp问题的解题思想，构建等效赋权矩阵。由于题目中所给的部分孔需要两种或两种以上的刀，并且对刀具的加工顺序有明确的要求，所以可以采取先将上述需要多种刀具加工的孔转化为若干个位置相同的单孔，并将不符合刀具加工顺序的孔的刀具转换费用置为的方式来处理问题。最后，得出使两个优化目标同时最优的方案。对于问题二，本问题同样属于双目标优化问题，相较于第一问，本问题从单钻头改为双钻头。两个钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。问题从单旅行商问题转化为了多旅行商问题。转换的同时的增添了一个约束，即在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。考虑到这一约束，应该建立模型在能够很好的解决合作间距问题的基础上使双钻头作业路线最优，得到最优的行进时间和作业费用。为使问题简化，可将两个钻头都看做质点，建立区域模型，将印刷版划分为5个区域，使得4个周围大区域中的单孔数目近似相等，区域中央通过半径为322cm的中心圆域将两个钻头的加工区域分开，从而能够满足约束条件。两个钻头按照区域模型所分配的加工区域进行加工后，为了节省总的作业时间，先完成的刀具再对中心圆域进行加工，这样可以使行进时间和加工费用同时达到最优。在解决双钻头加工的最优路线问题之后，运用同样的区域模型划分方法，只要改变中心圆域的半径，就可以很好的实现对两钻头合作间距的控制。分析打孔机的两钻头合作间距对作业路线和生产效能产生的影响。三.模型的假设及符号的说明3.1.模型的假设（1）假定对于同一孔型钻孔作业时间都是相同的。（2）假定钻头的行进速度是相同的。（3）假定针对不同孔型加工作业时，刀具的转换时间相同。（4）在计算两孔之间距离时，假设打孔机的钻头为一质点。（5）假定保持两钻头间距不小于3cm。（6）假定忽略钻头加工完一个区域转而加工另一个区域时移刀过程的行进费用。3.2.符号说明符号说明 eij判断i孔和j孔是否需要转换刀具w1刀具转换费用t11单钻头作业转换刀具的总时间liji孔和j孔之间的最短距离eij判断i孔和j孔是否在所求最短路径上w2钻头行进费用v单钻头行进的速度t12单钻头作业钻头行进的总时间w单钻头作业从i孔加工到j孔的加工费用t2双钻头作业的总时间w双钻头作业的总费用四.模型的建立与求解4.1.单钻头模型单钻头的线路板打孔问题可以描述为：钻头从起始点开始，不重复，不遗漏地加工完所有孔，最后回到起始点的过程。基于假设：对于每一个孔，用同一种刀具钻孔时间是固定的，本问题可以转化为一个典型的tsp问题。其中，钻头扮演了旅行商的角色。求解单钻头作业的最优作业线路，即求解在单钻头加工过程中，使得行进时间和作业费用同时最优的，钻头行进路线和刀具转换方案。建立模型分别对刀具转换费用和钻头行进费用进行求解，再建立优化模型求得最优作业线路下的最优费用。图1.单钻头作业费用划分图4.1.1 刀具转换费用将刀具a,b,ch依次标为1,2,38。已知相邻两刀具的转换时间是t=18 s用于加工的所给孔型有10种，每一种孔型加工时所用的刀具不完全一样，这就要求刀具在加工完一种孔型移动到另一种孔型的过程中是需要进行刀具转换的，这样就存在不同类型孔之间的换刀时间t1。由各刀具的位置关系可知，每次转动刀具所需的时间为a*t，其中a为由刀具位置关系所构造的刀具转换函数，用来判定在需要转换刀具时怎样转动可使转动费用和时间最短。考虑到从i孔(需要x种刀具)到j孔(需要y种道具)的刀具的所有转换情况为：fixfjy ，x,y1,2,3(1)fix表示打i孔需要x种刀具，fjy表示打j孔需要y种刀具。因为以个钻头有八个刀具，依次排列所以当换刀时，如何转换刀具需要通过判断得到。当ix转换到jy时，首先判断在钻头上通过两个刀具的劣弧转换刀具的数，若小于等于4，则直接通过劣弧转换刀具。若该数字大于4，则从另一边，也就是劣弧转换刀具。a= ix-jy , ix-jy4 8-ix-jy , ix-jy4 (2)10种孔型的类型中大部分是由多个刀具进行加工的，题目中说明不要求在加工完一个孔后才可以继续加工下一个孔。只要对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。说明钻头在加工需同一个类型的刀具的孔的前后不需要转换刀具。由此我们构建eij作为判断先后加工两个孔（i，j）是否需要转换刀具的函数。 eij= 0, 表示需不需要转换刀具1, 表示需要转换刀具 (3)综合以上刀具转换方式和转换时间的考虑，得出在整个单钻头加工过程中刀具的转换费用。(4)其中m=7元/min为刀具转换的时间费用。eij为判断是否转换刀具的函数。 转换刀具的总时间为t11=*t，其中为单钻头作业的最优线路中转换刀具的次数。4.1.2.钻头行进费用使用0-1规划模型判定从起始孔i孔到下一个孔j孔这条路径是否在所求的最短路线上，若在路线上则eij取1，否则取0。eij= 0 , 表示i,j不在得到的最优路径上1 , 表示i,j不在得到的最优路径上 (5)为使钻头的行进费用最少，需要找到每个刀具打完符合要求的所有孔的最佳行进路线，从而得到单个刀具加工的最少行进费用，加和后得到总的单钻头工作的最少行进费用。(6)其中，n=0.06元/mm为钻先后加工i孔和j孔行进单位路程所需费用, lij=xi-xj2+yi-yj2。钻头行进的总时间为t12=v，其中为单钻头作业的最优线路中路径的总长度，v为单钻头行进的速度。4.1.3.优化模型本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以上两个方面，即刀具的转换费用和刀具的行进费用，故建立以下优化模型来表征该类打孔机的生产效能，以同时得到使刀具行进费用w1和钻头转换费用w2同时趋于最小化的总加工费用w。minw=w1+w2(7)s.t.eij0,1eij0,1(8)通过式（9）我们得到从i孔(需要x种刀具)加工到j孔(需要y种道具)的加工费用w。4.1.4.基于tsp问题的等效赋权图旅行商问题旅行商问题（即tsp问题）也称最小哈密顿回路问题。假设gv,e,w表示带权连通图g，其中v为图g的结点集，e为图g的边集，w表示图g的边上权集合。货郎担问题就是求图g中使总权最小的，且通过每个结点一次而且仅一次的回路，也叫最小哈密顿回路。显然，若图g的n个结点表示n个同种类型的孔，边表示这n个孔之见的路径，每条边上的权表示相应路径的长度，则最小哈密顿回路就是同一种刀具依次打完所有需要符合要求的孔一次而且仅一次的最短回路。运用类似于tsp问题的解决方法，结合本题思想构建如下形式的等效赋权矩阵g，矩阵中所填数据表示从i孔转化到j孔所需的加工费用总和，即刀具转换费用和钻头行进费用的总和w1+w2。首先将重孔转化为单孔。如上所述把刀具a,b,ch依次标为1,2,38，然后对各孔重新进行编排。例：c1孔在加工时需要a,c两种刀具，则将c1孔转化为两个孔，即c11和c13两个孔。将各类型孔的所有待加工孔分别按照上述规则标号后全部列入下表，置于矩阵g左侧，表示正在加工的孔i；然后对该序列进行转置，置于矩阵g上侧，表示下一个进行加工的孔j。运用等效赋权矩阵将所有点之间的加工费用进行罗列，并进行全局搜索，寻找最优路线。表1.等效赋权矩阵 ji a11an1b11bn1c11c13c21jn3jn6a110wwwwwwww0an1w0b11w00bn1w0c11w0c13w0c21w00jn3w0jn6w0题目中条件限制，部分类型孔要求加工刀具有先后顺序之分。对于此类孔，再通过将重孔转化为单孔后，将其视为位置重合的单独的待加工孔，并通过下述方式对该重孔的刀具加工顺序加以限制。若加工孔时，不满足孔对刀具的加工顺序的限制，则将刀具转换费用w1置为无穷。即无需考虑行进费用w2，可直接将从i孔加工到j孔的加工费用w置为无穷。例：当加工完a11孔再加工c11孔时加工费用为w，（w=w1+w2），当加工完c11孔再加工c13孔时加工费用为w，（w=w2）当加工完c13孔再加工c11孔时加工费用为w，（w=）。4.1.5.模型的求解在构建上述等效赋权矩阵后，借助matlab软件，及tsp问题的思想，应用蚁群算法对模型进行编译得到使单钻头加工最优的如下方案。单钻头加工完所有类型的孔，为使加工费用最优化，我们需要得到刀具转换的最优顺序，从而得到刀具转换的最优费用。式（9）为单钻头加工最优路线时的刀具转换顺序。 cbabcaghfecefgh ababcdcbcbcdeca(9) hagefecfghaefe 单钻头加工时判断刀具的转换与否的0-1矩阵见附录1，按照优化得出的最优路径将所有单孔依次列出当0-1矩阵值为0时表示继续使用加工上一个孔所用的刀具，当值为1时，需要先进行刀具转换再加工下一个孔。题目要求给出单钻头加工的最优化线路，我们给出了刀具依次加工的孔的类型如下表所示。dcejcjdjcjcjcdede d edededcedc edcjc bcacbdjejfhcdej 注：由于点数太多，换刀顺序见附录一综合以上刀具转换的方案和行进线路的最优化我们得到如图所示的最优行进线路图。图2.单钻头最优行进路线图上图所示为我们最终求解得到单钻头最优路线图，考虑到使加工费用最低为优化目标，利用matlab编译并绘制出线路图，将单钻头加工所有加工孔的总路线加以呈现，其中黑色圆点为所有的过孔位置，红色连线为加工时钻头的行进路线。用这样的线路图使我们的结果更加直观、可感。图3.蚁群算法的循环收敛图应用蚁群算法，将若干只蚂蚁放在n个城市(过孔)上，每一只蚂蚁都依次选择城市（过孔），并随时更新蚂蚁行走时的信息量，找出所有只蚂蚁中，所走路径最短的值并保存。若循环的总次数没有达到最大的循环次数，则将继续转到第二步执行，若满足结束条件循环将结束，同时输出结果数据。由图2中蓝色折线所示，通过不断的增加循环次数，可以发现所走的路径的最小值有减小的趋势。当循环次数为1时，最短路径较长，而当循环次数上升至80至100次后最短路径的平均值收敛至最小，并趋于平稳。红色折线将收敛过程中最优路径的平均值很好地呈现出来。最后，题目中所求的单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业费用以下表呈现。表2.单钻头作业最优线路时间/s费用/元路程/mm换刀次数/次刀具转换79292.444钻头行进83.4900.75150125.5总和993.15150125.5444.2.双钻头模型基于问题一的问题条件和模型求解结果我们构建了问题二的模型。问题二为双钻头加工优化问题，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。考虑到题目中增添的限制条件,两钻头合作间距不小于3cm。首先，为控制使双钻头加工的路径和时间同时得到最优，我们将由问题一所述方法得到的，印刷板上所有的孔即aj孔的位置信息和所需刀具的各项信息进行了分析及统计。并引用matlab软件绘制了如图（3）所示的所有孔的分布图。由图3可知aj孔分布在图中的整个区域中，为了简化问题将钻头均视为质点。通过对所有孔的位置及所需刀具的分析，即只要在满足限制条件两钻头合作间距不小于3cm的前提下，刀具的形状等因素均不会影响印刷板的的加工。采用模型一中的方法，将所有需要多种刀具加工完成的重孔，全部转换为单孔。图4.所有孔的分布将整个线路板看做一个加工的区域，由于本问题是用两个钻头同时进行加工，在满足合作间距大于3cm的前提下，两钻头可以同时作业，且作业是独立的。我们对整个加工区域进行划分，使两个钻头只要分别按照第一问所求得的单钻头加工方案，来加工所划分的区域，就可以得到双钻头加工的最优路线。4.2.1.双钻头加工的区域模型划分的区域模型要同时满足作业线路最优和3cm的限制条件。对此，首先尝试划分如图6所示的区域模型。划分时，控制使左右两个大区域内的单孔数目近似相等，中间区域的宽度控制为3cm。中间区域的设计是为了满足双钻头加工时的合作间距大于3cm这一限制条件。两个钻头同时开始加工，按照第一问所求解的单钻头作业方式对左右两个大区进行加工。因为孔数及转刀次数、行进路径长度等因素的限制，会有一个钻头先完成所划分区域内过孔的加工。为了节约总的加工时间，将这个钻头转而继续加工中间区域。经过分析、讨论，这种区域划分方法可以满足3cm的限制条件，但是不能很好的使作业线路最优。由于中间区域过大，会使得在很长的时间内只有单个钻头在进行加工，这样会使得钻头的行进时间增长，加工费用也会在一定程度上增加。图5.区域模型为了使所划分的区域模型，在满足限制条件的前提下使作业方案最优，要尽可能得减小中间控制区域的大小。4.2.1.区域模型的优化经过实验、分析得到当把中间区域建立为一个以x=0;y=270000 mil/100和以（x,y）=（0,270000）为圆心，以3/sqrt(2)cm为半径划分出来的中心圆域时，可以满足所有条件。为控制使双钻头加工的路径和时间最优，我们对孔的分布进行了统计与计算。将整个线路板划分为四个主要大区域，即area11、area12、area21、area22，使得每个区域的单孔的个数尽量相等，以使得两个钻头分别的加工时间尽可能的接近。其中区域area11和area12由钻头一加工完成，area21和area22由钻头二加工完成。为满足题目中所述的限制条件我们增加了如下图所示的中心圆域。经过多次区域划分实验，发现x=0;y=270000 mil/100和以（x,y）=（0,270000）为圆心，以3/sqrt(2)cm为半径划分出来的中心圆域，可以再不影响求解双钻头加工的最优方案的前提下很好地控制题目中所给的限制条件，即在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。图6.优化区域模型将两个钻头同时开始加工，从中心圆域的圆周上的点为起点。钻头一从区域area12开始加工，将该区域中所有单孔按照问题一中的加工方式加工完毕后，接着加工区域area11的所有单孔，同样采用问题一所求解得到的最优加工线路及方案进行加工。与此同时，钻头二从中心圆域的圆周上的点出发依次加工区域area21和area22内的所有单孔。忽略钻头加工完一个区域转而加工另一个区域时移刀过程的行进费用。待有一个钻头加工完毕后，用该钻头继续加工中心圆域中的单孔，加工的方法与上述方法相同。由于两个钻头以对角线的方式在同一时间加工的孔的区域由中心圆域相隔开，从而避免了在加工的任何时候两个转头的间距小于3cm。在其中一个钻头加工完毕后直接加工中心圆域中的孔，这样既节约了时间也满足了题目所给的限制条件。由于两个钻头工作是相互独立的，且合作间距已知不小于3cm。因此在解决双钻头最优作业方案时基础上再加上另一个钻头作业所需的各种费用并增加约束条件，保证合作间距在要求范围之内。若钻头1打i孔时钻头2打i孔，记i孔与i孔之间的距离为lii=（xi-xi)2+（yi-yi)2(10)minw=w1+w1+w2+w2(11)s.t.eij0,1lii1181i,j,i1,2,n(12)其中w为双钻头加工的最优线路的加工费用。4.2.2.模型的求解按照上述模型将双钻头的双目标优化问题很好地转换成了与问题一中的单钻头优化问题近似的问题，所以在对模型进行适当的分析和调整后我们依次得到了两个钻头加工前四个方形区域的最优加工线路。其中钻头一加工的area11、area12的左半区域最优加工回路图如下所示。图7.左半区域行进路线其中上方的图为单钻头按照第一问所求解的方法对于area12的加工回路图，下方的图为area11的加工回路图，在钻头一加工完area12后，直接移到area11进行加工。钻头二加工的为印刷板所分成的四个区域的右半区域。即area21和area22。右半区域的加工回路图如下所示。图8.右半区域行进路线其中上方的图为area21的加工回路图，下方的图为area22的加工回路图，在钻头二加工完area21后直接移到area22进行加工。两个钻头分别加工自己的两个区域，由于点的总数及换刀次数等限制条件的影响，两个钻头会有一个先完成。为了节省总的加作业时间将先完成的钻头转而继续该整个线路板中心圆域，从而使双钻头加工的总时间和总费用最优。图9.中心区域行进路线上图所示为单钻头加工加工中心区域中的孔时刀具的行进路线。待两个钻头分别加工完所有印刷版上的所有孔后，我们对加工各区域时刀具的转换费用、换刀次数、钻头的行进费用、行进时间分别进行了计算，得到双钻头打孔机的最优作业路线。所得数据如下表所示。表3.双钻头作业最优线路区域area11area12area21area22中心圆域合计行进距离/mm2891.66737651863.3332698.333163.333311381.67行进时间/s16.0648120.9166710.3518514.990740.9074163.23148行程费用/元173.5225.9111.8161.99.8682.9换刀次数/次1014814349换刀时间18025214425254882换刀费用/元2129.416.829.46.3102.9总费用/元194.5255.3128.6191.316.1785.8上表所示为问题二的第一问所求的双钻头作业的最优线路数据。图10.单钻头与双钻头作业对比图由图8可知，与传统单钻头相比，无论在行进时间还是换刀费用上，双钻头作业的方式都有了明显的提高。为了更加明确的将两种加工方式进行比较我们对生产效能各方面的提高分别进行了计算。行进时间效能：=t2-t12t1*100%=63.2-83.483.4*100%=-24.2%(13)即当采用双钻头作业时作业时间相较于传统的单钻头作业减少了24.2%。作业费用效能：=w-ww*100%=785.9-993.15993.15*100%=-20.87%(14)即当采用传统的的单钻头作业方式和双钻头作业方式时，双钻头作业的加工费用明显小于单钻头作业费用，费用降低了20.8