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

打孔机生产效能的提高摘要过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本题旨在研究某类打孔机的最优作业路线（包括刀具转换方案）、行进时间和作业成本，从而寻找提高打孔机的生产效能的方法。针对问题一，我们考虑到钻头行进速度、行进成本和刀具转换时间成本不变，因此我们只要求出钻头行进的最短路程和刀具的最少转换次数即可，刀具的转换次数最少的顺序为：。这样不仅降低了刀具转换成本，而且使得刀具转换时间缩小到最少。对于求解最优作业路线的问题，我们建立了关于路线的优化模型，运用模拟退火算法来模拟出了钻头的行进路线，最后算出单钻头过孔的最优路线的行进时间为1674.12s，作业成本为961.872元。针对问题二，双钻头的打孔机作业时相互独立，但为了避免钻头间的干扰，我们采取了分区域的做法，将两个钻头分区域来工作。根据分析，我们将整个线路板分成4个区域，A钻头在2，4区域工作，B钻头在1，3区域工作，此时刀具转换次数最小时的顺序为：。求解方式与第一问相似，经过模拟退火算法模拟得到最优路线的行进时间为990.21s，作业成本为1304.77元，生产效率提高了40.86%。当考虑到打孔机的两钻头合作间距对作业路线和生产效能的影响时，我们的结论是适当的减小两钻头之间允许的间距，其作业路线和成本都会达到更优，提高了生产效能。关键词：生产效能 最优作业路线 转换次数 模拟退火算法一、 问题重述1.1 问题的背景过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。 由于过孔的加工费在整个制板费用中是一个不小的开支，在保证产品质量的前提下，生产厂商当然会在减小过孔加工费的问题上下工夫，以谋求更大的生产利益，这也就促使很多人开展缩短钻头的作业路线的研究。我们通常用以下几个方面来刻画打孔机的生产效能：（1）单个过孔的钻孔时间，我们假定同一孔型钻孔作业时间是相同的，（2）打孔机在加工作业时，钻头的行进时间，（3）对不同的孔型加工作业的时候，刀具的转换时间。本文旨在研究一个钻头在一块印刷线路板上加工完所有孔的最优路线（包括刀具转换方案）、行进时间以及工作成本，为了提高打孔机的效能，现有一种双钻头的打孔机，题中也要求我们给出双钻头打孔机的最优作业路线、行进时间和作业成本，并且与传统的单钻头打孔机比较生产效能。1.2 需要解决的问题分析附件中的数据，我们需要解决如下几个问题：1) 根据附件1提供的某印刷线路板过孔中心坐标的数据，解出单钻头作业的最优作业路线（包括刀具转换方案）、行进时间和作业成本。2) 为提高打孔机的工作效能，设计出一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时工作，且作业时独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为了避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距3cm。并且也要给出双钻头作业时的最优作业路线、行进时间和工作成本，并且与传统单钻头打孔机进行比较其生产效能。并且研究打孔机的双钻头合作间距对作业路线和生产效能的影响。二、 问题分析针对问题一，这是一个优化问题，我们主要考虑钻头行进的成本和时间，以及转换刀具的成本和时间。我们需要找到走遍所有点的最优路径，从而使打孔机的生产效能达到最高。首先我们得到附录中各种孔型的孔的分布情况，然后根据这个分布情况选择使用刀具顺序。而且根据题中随后要求我们求的单钻头作业的最优作业路线（包括刀具转换方案）以及已知钻头行进速度，行进成本和刀具转换时间成本不变，我们只要求出钻头行进的最短路程和刀具的最少转换次数即可，这样就可以达到最小的成本，我们采用模拟退火算法得到了这个优化模型的解。为了提高打孔机的效能，现在设计出了一种双钻头的打孔机（其中每个钻头的形状与单钻头的形状相同）。这两个钻头可以同时工作并且工作独立，为了避免钻头之间的碰撞和干扰，在加工过孔的任何时间都必须保持两钻头间距不小于3cm，因此我们将整块线路板按照横坐标来分成这样4个区域。在这四个区域（，）内分别按照模拟退火算法算出其最优作业路线、行进时间和作业成本。最后将这些数据做一个总和，然后与第一问中的数据进行比较，从而得出两种钻头的生产效率。最后除了将各种孔型之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一种孔型的第一个点坐标相连之外，还要将同一个钻头在上一个区域的终点与下一个区域的起点相连，即得到钻头行进的最优路径。总的来说这里也是一个优化的过程，找到走遍所有点的最优路径，使得打孔机的生产效能达到最高。三、 模型假设与符号系统3.1 模型的假设1) 所有孔型的钻孔作业时间都是0.5s。2) 第二题中的A钻头跨区域的时候与B钻头的距离都大于0.3cm。3) 钻头行进过程平稳，不发生故障，方向可以任意改变。4) 钻头的行进速度是一个常数。3.2 符号系统表3.2 符号系统符号含义单钻头对不同孔型钻孔作业时间不同孔型所需要钻孔的总数单钻头钻孔作业的总时间钻头行进的总时间刀具的转换时间作业成本行进成本刀具转换成本行进总路程四、 问题一的建模与求解4.1 问题一的分析本题是一个优化模型，主要考虑钻头行进的成本和时间，以及转换刀具的成本和时间。我们需要找到走遍所有点的最优路径，从而使打孔机的生产效能达到最高。为了确定钻头行进的最短路程，我们首先将题目中提供的印刷线路板过孔中心坐标的数据利用matlab画出了坐标分布图，发现同种孔型以及不同种孔型的过孔分布有密集也有分散。而且根据题中随后要求我们求的单钻头作业的最优作业路线（包括刀具转换方案）以及已知钻头行进速度，行进成本和刀具转换时间成本不变，我们只要求出钻头行进的最短路程和刀具的最少转换次数即可，这样就可以达到最小的成本。我们采用模拟退火算法来解决这个问题，因为模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突破性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。运用模拟退火算法我们求出各种孔型各自分布点的最短路径及路径的首尾坐标。我们通过穷举法，找到了最优的刀具转换方式，并因此确定各种孔型之间的打孔顺序。最后我们根据各种孔型之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第一点坐标相连，即得到钻头行进的最优路径。4.2 数据预处理首先我们将题目中的密尔转换成1/100毫米，这样便于后面的直接计算，这个过程可以直接在excle中实现。表4.2.1 将所有数据单位统一（有删节）A （660个）B （788个）C （270个）D （212个）E （95个）256187-25459164-279410668-442112025920320-2547645-25655136-312913305-4421374264719522-25456248-25655278-3139106685691118271321265-25458189-25655405-326611976569137229111153-25703119-2565553233178138-69611203185711-25746735-25655669-331711257-6961374320521478-257468152565901733226670-741120324122692-25746895-2570381-335810394-74137433177656F （34个）G （20个）H （6个）I （10个）J （29个）-7907848-7653-48880622784-75065859-734115174-7907-1331-765359480624333-75067059-734117714-79071887-7653-1077-811399445991159378311-787-7907-234-76531102-8113115955991211378311175375619992-7653-1585-134133581244615567-77951013575621262-76531633366133581244621507-77951140576117955-765320-699677018367298776119225-76532141-6996924183674130107419992-8161-488-7554770125402540107421262-8161594-75549241254011730下图中是以1/100毫米为单位，并且横着的是纵坐标，竖着的是横坐标。我们在matlab 中实现这些点的分布图如下：图4.2 不同孔型的分布情况（单位1/100毫米）在这个图中，我们将不同类型的孔用不同的颜色标注出来，我们大致可以得到各种孔型的分布情况。为了尽量减少印刷线路板过孔的成本，应减少转换钻头的次数，而且还要寻找最优的作业路线。那么首先我们要将转换钻头最少次数的方案找出来。4.3 模型的前期准备模拟退火算法模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火）,粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态i之下的能量为E(i)，那么材料在温度T 时从状态i进入状态j 就遵循如下规律：（1）如果，接受该状态被转换。（2）如果，则状态转换以如下概率被接受：其中K是物理学中的波尔兹曼常数,T是材料温度。在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i的概率满足波尔兹曼分布：其中 x 表示材料当前状态的随机变量， S 表示状态空间集合。显然其中| S |表示集合S 中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时，其中上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题：优化函数为，其中，它表示优化问题的一个可行解，S 表示函数的定义域。表示x的一个邻域集合。首先给定一个初始温度和该优化问题的一个初始解x(0)，并且x(0)生成下一个解，是否接受作为一个新解x(1)依赖于下面概率：换句话说，如果生成的解x的函数值比前一个解的函数值更小，则接受作为一个新解。否则以概率接受x作为一个新解。泛泛地说，对于某一个温度和该优化问题的一个解x(k)，可以生成x。接受x作为下一个新解x(k +1)的概率为： （1） 在温度下，经过很多次的转移之后，降低温度，得到。在下重复上述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。我们注意到，在每个下，所得到的一个新状态x(k +1)完全依赖于前一个状态x(k)，可以和前面的状态x(0), x(k 1)无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态x(k)生成x的概率，在N(x(k)中是均匀分布的，且新状态x被接受的概率满足式（1），那么经过有限次的转换，在温度下的平衡态 的分布由下式给出： （2）当温度T 降为0 时，的分布为：并且这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1 被找到。因此可以说模拟退火算法可以找到全局最优解。在模拟退火算法中应注意以下问题：1) 理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。2) 要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m 次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值，或连续几个温度下转换过程没有使状态发生变化算法就结束。3) 选择初始温度和确定某个可行解的邻域的方法也要恰当。4.4 模型的建立我们通过穷举的方法得到刀具转换次数最少的转换顺序为：同时我们可以知道不同孔型的打孔次序为：DG表示刀具d只完成了这两种孔型的第一道工序，DI则表示刀具e完成了D孔型的第二道工序和I的第一道工序，J表示刀具f完成了这种孔型的第一道工序，以此类推。解空间S可以表示为1,2，.，2813,2814的所有固定起点和终点的循环排列，其中每一个循环排列表示侦察2814个目标的一个回路，表示在第i次侦察j点，初始解可选为（1,2 ，,2814）。目标函数为钻头所走的最短路线，我们要求这就是我们所列出来的优化模型，那么接下来就利用模拟退火算法来进行优化。4.5 模型的求解模拟退火算法每一次迭代由下面三步构成：1）2变换法：任选序号u,v（uv）交换u和v之间的顺序，此时的新路径为：2）3变换法：任选序号u、v和w，将u和v之间的路径插到w之后，对应的新路径为（设uvw）3）代价函数差：对于2变换法，路径查可以表示为4）接受准则5）如果，则接受新的路径。否则，以概率接受新的路径，即若大于0到1之间的随机数则接受。6）降温：利用选定的降温系数 进行降温即：T T ，得到新的温度，这里我们取 = 0.99。7）结束条件：用选定的终止温度，判断退火过程是否结束。若T e，算法结束，输出当前状态。我们通过模拟退火算法得到如下结论：表4.5.1 单钻头作业的最优作业情况刀具孔型起点终点行进路程行进时间aAC(113.74,148.18)(113.71,227.81)3129.217.38444bB(-54.15,165.35)(-6.88,177.55)2892.116.06722cCEIJ(124.45,215.07)(124.45,155.67)2602.814.46dDG(22.56,233.63)(-65.56,206.73)1293.27.184444eDI(22.56,233.63)(-65.56,206.73)1313.57.297222fJ(-68.17,-16.56)(25.6,-16.56)1078.45.991111gFG(-76.53,21.42)(1.26,179.55)622.93.460556hFH(3.66,133.58)(80.62,27.84)652.83.626667fEG(-7.21,75.59)(69.06,103.25)1030.95.727222表4.5.2 单钻头作业的行进成本刀具abcdefghf行进成本187.752173.526156.16877.59278.8164.70437.37439.16861.854钻孔次数930788404232222295440115以下为单钻头作业的不同刀具的轨迹图 图4.5.1 刀具a轨迹图 图4.5.2 刀具b的轨迹图图4.5.3 刀具c轨迹图 图4.5.4 刀具d轨迹图 图4.5.1 刀具e轨迹图 图4.5.1 刀具f第一次轨迹图 图4.5.1刀具g轨迹图 图4.5.1 刀具h轨迹图图4.5.1刀具f第二次轨迹图现假设单钻头对不同孔型钻孔作业时间分别为 ，在数据预处理中我们就可以知道不同孔型所需要钻孔的总数分别为：c1=660，c2=788，c3=270，c4=212，c5=95,c6= 34，c7=20，c8=6 ，c9=10 ,c10=29，那么单钻头钻孔作业的总时间为：钻头的行进时间为：刀具的转换时间为（由于钻头只需要转换10次，所以转换时间将会是一个定值）：由前一种刀具过孔的终点到下一种刀具过孔的起点（即刀具转换）之间钻头所行进的总路程为1065.4mm，得到行进时间：钻头行进的总时间：现假定所有孔型钻孔作业时间都是相同的，每次钻孔所花的时间为0.5s，那么单钻头钻孔工作的总时间为：加工一块线路板所需要的总时间为：作业成本=行进成本+刀具转换成本=876.948+21+63.924=961.872元4.6 结果的分析通过模拟退火算法我们得到了最佳的刀具转换方案：；同时我们得出了不同刀具的最短行进路线，当把所有的刀具的最短路线相加即为整个钻头工作的最优作业路线；最后我们得到了加工一块线路板所需要的时间为1674.12s，其中钻头的行进时间为87.12s，由此可见我们假设的钻孔时间对加工线路板的总时间影响很大，所以加工厂除了对钻头行进线路做优化，也应对加工设备的维护和更新上做一定的研究。最终我们得到作业成本为961.872元，其中钻头运行费用为940.872元，占了绝大部分，说明优化运行路径对与节省费用是很重要的。五、 问题二的建模与求解5.1 问题的分析为了提高打孔机的效能，现在设计出了一种双钻头的打孔机（其中每个钻头的形状与单钻头的形状相同）。对于这两个可以同时工作并且相互独立的钻头，为了避免钻头之间的碰撞和干扰，在加工过孔的任何时间两个钻头之间的距离都必须不小于3cm，由此我们将整块线路板按照x坐标来分成这样4个部分，-82.65mm -30.87mm ， -30.87mm20.90mm， 20.90mm72.68mm, 72.68mm124.45mm。由此在这四个区域（，）内分别按照模拟退火算法算出其最优作业路线、行进时间和作业成本。最后将这些数据做一个总和，然后与第一问中的数据做比较，从而得出两种钻头的生产效率。在不同的区域内，我们发现同种孔型以及不同种孔型的过孔分布有密集也有分散。而且根据题中随后要求我们求的单钻头作业的最优作业路线（包括刀具转换方案）以及已知钻头行进速度，行进成本和刀具转换时间成本不变，我们只要求出钻头行进的最短路程和刀具的最少转换次数即可，这样就可以达到最小的成本。最后除了将各种孔型之间的打孔顺序将前一种孔型求出的最短路径的最后一点坐标与后一孔型的第一坐标相连之外，还要将同一个钻头在上一个区域的终点与下一个区域的起点相连，即得到钻头行进的最优路径。总的来说这里也是一个优化的过程，找到走遍所有点的最优路径，使得打孔机的生产效能达到最高。这是由于所要打的孔型的孔的总数是一定的以及单个过孔的钻孔时间是一定的，那么只有打孔机钻头的行进时间和加工不同孔型时刀具的转换时间会影响到打孔机的生产效能，所以我们针对这两个因素来考虑生产效能。5.2 模型的建立相互独立的双钻头打孔机为了避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm，因此我们将整个线路板分成四个区域，设两个钻头分别为钻头A和钻头B，钻头A行走区域、，钻头B行走区域、，当钻头A走区域的时候钻头B走区域；当A行走完区域就直接去行走区域，而不用等待钻头B，钻头B不论什么时候走完区域就可以开始走钻头B的第二个区域。根据各个区域的各种孔型的分布特点，得出各个区域刀具转换顺序为：它所对应的孔型的顺序为：在钻头A行走区域、中，这8种刀具所对应的孔的个数分布为：表5.2.1 8种刀具在区域中对应的孔的分布刀具dcbahgfec孔型DGEBACFHFGEGJDICIJ孔的个数105433505007857106150在钻头B行走的区域中，这8种刀具所对应的孔的个数的分布：表5.2.2 8种刀具在区域中对应的孔的分布刀具dcbahgfec孔型DGEBACFHFGEGJDICIJ孔的个数12348436408334678112146首先我们建立目标函数，这是一个优化模型，如下：其中只是赋予时间和行走路线的权重，我们只需要算出最优作业路线和行进时间即可，这个求最优解得过程主要是依靠模拟退火算法来实现。5.3 模型的求解表5.3.1 钻头AB的最优路程刀具dcbahgfec孔型DGEBACFHFGEGJDICIJ区域路程1022.7719.724162371.6666.2733.51055908.81196.9区域路程888.39599.271921.72837.36131.23476.93872.76932.311365.88总线路1911.091318.974337.75208.96797.431210.431927.761841.112562.78由此我们找出同种刀具在两个区域中所行走的较长的那个路程，从而求出这种刀具的这种打孔机钻头的行进时间表5.3.2 不同刀具的行进时间刀具dcbahgfec孔型DGEBACFHFGEGJDICIJ行进时间5.68163.998313.42215.7633.70114.0755.86115.17957.5882表5.3.3 决定打孔时间的孔数刀具dcbahgfec孔型DGEBACFHFGEGJDICIJ区域孔的个数105433505007857106150区域