打孔机生产效率的提高

1参赛组员系班系班2D题打孔机生产效能的提高目录摘要.............................................................................................................3一、问题的重述........................................................................................4二、问题的分析........................................................................................6三、模型假设.............................................................................................7四、符号说明.............................................................................................8五、模型的建立和求解............................................................................9六、模型的优化......................................................................................12七、模型的评价......................................................................................14八、参考文献...........................................................................................15附录：.......................................................................................................153摘要本文对印刷电路板过孔的生产效益如何提高进行了研究。打孔机在加工作业时，影响生产效益的因素主要有：单个过孔的钻孔作业时间，打孔机的钻头在作业时的行进时间以及刀具的转换时间。在完成一个电路板的过孔加工时，由于题中已假定同一个孔型钻孔作业时间都是相同的，所以钻头行进时间和刀具转换总时间越短，费用越少，生产效益越高。钻头行进总时间由钻头进行路线决定，而刀具转换总时间由线路板上由各孔的位置以及钻头行进方案决定。本文中首先采用了0-1整数规划方法（模型一），再采用二次逐`边修正法（模型二），之后采用了贪心算法（模型三）。在求解过程中，我们先考虑只打孔的情况，即遇到孔便打完，同时以最少费用为目标，对这三个模型进行比较，结果如下：模型一：该模型的变量较多，且使用0-1规划法。即令0,1ije，当1ije，表示(,)ij在得到的最优路径上；当0ije，表示(,)ij不在得到的最优路径上。通过这个变量建立起路线与费用的桥梁关系，进而写出总费用的表达式，建立最优模型，用遗传算法求解。4模型二：在以最少费用为目标的条件下，费用为79232元，时间为49188秒（约合13.66小时）。模型三：在以最少费用为目标的条件下，费用为44708元，时间为48665秒（约合13.5小时）。在以最少时间为目标的条件下，费用为374090元，时间为56298秒（约合15.6小时）。在模型的优化部分，本文将需要两种刀具（或三种）的孔视为两种孔型（或三种），如C型孔，视为C1和C2两种孔型，分别用a刀和c刀（有下刀顺序），D型孔视为两个独立的孔D1和D2（无下刀顺序）。同时综合考虑费用和时间，建立适合大规模生产的模型，取合适的权值（以费用60%、时间40%为例），费用为49276元，时间为21272秒（约合5.9小时）。一、问题的重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实5际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。现有某种钻头，上面装有8种刀具a，b，c，…,h，依次排列呈圆环状，如图1所示。图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次bcdefgha6序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fHe,cf,c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。请建立相应的数学模型，并完成以下问题：（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1inch=1000mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。二、问题的分析本题的主要问题，是考虑行走的费用、时间以及转刀的费用、时间，找到一条遍历所有点的合适的行走路径，使生产的效率达到最高。在MATLAB软件中，我们画出了这十种孔型的坐标（见附录1），发现孔的数目很多，既有集中的孔，也有相对分散的孔。因此，所建的模型，应该要将所有的点都走遍，这一点可以参照TSP的相关算法，同时考虑到各种换刀问题。从收集的资料可以看出，解决TSP问题7的一般算法有遗传算法，模拟退火算法，贪心算法，二次逐边修正法等等。考虑到本题并不是完全意义上的TSP问题，本文对使用的方法进行了一定程度改进，例如考虑将路程和转刀的因素统一成时间或是费用，使其更适合本题的要求。考虑到本题要求得出打孔的费用和时间，因此有不同生产效率的生产线，对费用和时间有不同的要求，因此在模型求解的过程中应该要考虑到对费用和时间赋予不同的权数，得出不同的行走方案，最终确定符合要求且效率高的行走路径和转刀方案。三、模型假设1、加工每块板工作过程中，无刀具磨损、损坏情况，中途无间断。2、钻头钻孔、刀具加工的结果均合格，不存在残品孔。3、钻头钻孔时间及费用固定，不予考虑。4、刀具行进速度保持恒定。5、周围环境对钻头和刀具没有干扰。6、钻头和刀具可以按照设定的路程准确行走和换刀。7、刀具行进过程中两点之间所走路径为直线。8四、符号说明m：点的数目（2124个）。M:将孔拆分后点的数目（2814个）。Wij:为0-1变量，Wij=1表示，i点可到达j点，Wij=0表示，i点不能到达j点。Lij:移动的费用加换刀具的费用。Ni:为0-1变量，保证有m-1条折线。mm：转刀费用矩阵（10*10）。mm1：转刀费用矩阵（18*18）。x：点的横坐标。y：点的纵坐标。S1：i点到j点的费用（包括路程费和转刀费）。S2：i+1点到j+1点的费用（包括路程费和转刀费）。S3：i点到i+1点的费用（包括路程费和转刀费）。S4：j点到j+1点的费用（包括路程费和转刀费）。S(i):i点到i+1点的费用（包括路程费和转刀费）。F(i):i到i+1点所用时间（路程所用时间和转刀所用时间中较大的一个）。fare：总费用。V1：fare权数。time：总时间。9V2：time权数。五、模型的建立和求解（1），模型一的建立（0-1规划模型）通过以上分析，我们建立了模型一，综合考虑总路程与总费用，通过0-1规划思想来求取最优解。11ij11**min11111mNiWjiWWijWijNiLijWijmimjmimimj其中m11**minimjNiLijWij表示最小费用的目标函数。1m1iWij表示回路只能到达各顶点一次。1m1jWij表示回路只能从各顶点出发一次。1WjiWij表示两点之间只有一条路径连接。模型一从0-1整数规划角度给出了一个只考虑总回路路程最短的M-TSP问题模型。对于这样一个规划问题，每个分组对应着一个TSP10问题，相关资料显示，由于数据量特别大现有的Lingo和Matlab软件不能求解或不能精确求解，故该模型只有理论意义，不能在现有的软件下实现。下面讨论用一些简化的方法来求得问题的近似解。（2）模型二的建立（二边逐次修正法）1、按照附件中给定点的顺序在坐标纸上将各点依次连接，命名为路径a1。2、对所有的i、j，1i+1jm,若S1+S2S3+S4,则在a1中删去路径i到i+1和j到j+1两条路径，而选择i到j和i+1到j+1两条路径，形成新的路径a2。3、重复步骤（2），直到满足条件，最后的路径即为所求的路径a。4、计算总的费用：1.2*)1,(001524.0*2))^(y-)1((2))^()1(()i(iimmiiyixixS1-m1i)i(fareS其中mm矩阵如下（不考虑换刀时的转刀费（从竖列到横行））：DC，表示D打完到C打完，需要换刀六次。ABCDEFGHIJA0124537166B1033446257C214235534611D4362535324E3453626233F1235628055G3453626233H1235628055I2142355346J2142355346取得路径a之后即可求解出最小费用。结果表明：以最小费用为目标，需要79232元，时间为49188秒（约合13.66小时），具体的行走路径、路径图及程序见附件1(按点给出初始顺序依次排序为1号到2124号，打孔的顺序即按编号排列，附件2、3同样)。（3）模型三的建立（贪心算法）1、选择一个起点，计算这个起点到其它各点的费用（路程费加转刀费），选择费用最小的一个点作为下一个起点，计算费用S(1)。2、计算新的起点到其它点的费用（不包括已选定的点），选择费用最小的点作为下一个起点,计算费用S(2)。3、重复步骤2，直到遍历各点,求出相应费用S(i)。4、计算总的费用：1.2*)1,(001524.0*2))^(y-)1((2))^()1(()i(iimmiiyixixS1-m1i)i(fareS)18*)1,(,180/0254.0*2))^(y-)1((2))^()1((max()i(iimmiiyixixF121-m1i)i(timeF结果表明：