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

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 中 南 大 学 参赛队员 (打印并签名) ：1. 陈 帆 2. 杨富龙 3. 汪 潮 指导教师或指导教师组负责人 (打印并签名)： 易昆南 日期： 2012 年 8 月 21 日赛区评阅编号（由赛区组委会评阅前进行编号）：2006高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：打孔机生产效能的提高【摘要】通过对影响印刷电路板打孔机生产效能因素的分析，得出影响打孔机生产效能的因素主要是刀具的转换时间和钻头的行进时间。分别利用穷举法和现代优化算法对刀具的转换顺序和钻头行进路径进行优化，得到最佳的刀具转换顺序和钻头行进路径，以缩短刀具转换和钻头行进的时间，从而达到提高打孔机生产效能的目的。影响打孔机生产效能的因素主要有：单个过孔的钻孔作业时间；打孔机在加工作业时，钻头的行进时间；针对不同孔型加工作业时，刀具的转换时间。其中单个过孔的钻孔作业时间是由生产工艺决定的，要想减小此因素对打孔机生产效能的影响，就必须提高打孔机的生产工艺，所以此因素不在本文的考虑范围内，本文主要就后两个因素进行分析，因此分别建立了以总加工费用最少和总加工时间最短为目标的线性优化模型，。其中为总加工费用，为刀具转换费用，为钻头行进费用，为总加工时间，为刀具转换时间，为钻头行进时间。其中刀具转换的费用和时间可通过优化刀具转换顺序来优化，钻头行进费用和时间可通过优化钻头行进路径来优化。钻头行进路径的优化是典型的旅行商问题，属于组合优化问题，可利用蚁群算法，模拟退火法，遗传算法等现代优化算法进行求解。由于本题的数据比较小，而蚁群算法又具有局部搜索速度快、收敛性良好的优点，所以本文采用蚁群算法对本问题的最优线路和最短路径进行求解，用模拟退火法，遗传算法对蚁群算法进行优化和检验。问题一：打孔机单钻头行进作业时，先根据钻头上各个刀具的分布情况，结合各孔型对刀具的具体要求，利用穷举法找出最佳的刀具转换顺序。在最佳刀具转换顺序的前提下，利用蚁群算法找出钻头的最佳行进路径。然后分别计算刀具转换和钻头行进的时间和作业成本再对结果进行汇总，则所求结果即为最优解。问题二：对于双钻头打孔机，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距），为了保证两钻头间距不小于3cm。将整个电路板分成一，二，三三个区域，（如图5-6所示），其中一，三区中点的距离始终大于3cm，所以可以令两个钻头分别在一区和三区同时作业，这样就节省了加工时间。当一、三区的孔都打完时，再打二区的孔。对于二区，则采用双钻头交替打孔的方案，即前一个钻头打孔时，下一个钻头转换刀具，前一个钻头打完孔后，下一个钻头继续打孔，如此交替操作。然后求出双钻头打孔的方案下钻头的行进时间和总的作业成本，与问题一进行比较。最后发现双钻头同时打孔并不能使打孔机的生产效能得到提高，所以又提出了双钻头交替打孔的方案。对于转换刀具时从一类刀具打出的最后一个点与下一个刀具的第一个点的距离可能不是最优路径，所以本方案可能不是全局最优解而是接近全局最优解得局部最优解。关键字：穷举法 组合优化问题 蚁群算法 局部最优 交替打孔一、问题重述1.1 基本情况过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。本问题旨在提高某类打孔机的生产效能。打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业，即一个钻头进行打孔。现有某种钻头，上面装有8种刀具a，b，c， , h，依次排列呈圆环状，如图1所示。bcdefgha图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18 s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型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：某一印刷线路板过孔中心坐标的数据(数据以1/100mil为单位，1mil=0.0254mm)；1.3 问题提出请根据这些数据资料，利用数学建模的方法，解决如下问题：（1）根据附件1的数据，给出单钻头作业的最优作业线路（包括刀具转换方案、行进时间和作业成本）；（2）根据附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？；（3）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、问题分析打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定；（2）针对不同孔型加工作业时，刀具的转换时间；（3）打孔机在加工作业时，钻头的行进时间。其中单个过孔的钻孔作业时间是由打孔机的生产工艺决定的，要想减小单个过孔的钻孔作业时间对打孔机生产效能的影响，就必须提高打孔机的生产工艺，这不在本文的研究范围内。本文主要研究后两个因素对打孔机生产效能的影响。由于所给的印刷电路板包含所有的孔型，而要完成这些孔型的打孔则需要用到所有的刀具。针对不同孔型加工作业时，刀具的转换时间与刀具的转换顺序有关，通过穷举法可以找到打孔机钻过所有孔刀具的最佳转换顺序，其最佳转换顺序是：。最优刀具转换顺序是指将刀具转换到各孔型所需要刀具所用时间最短的刀具转换顺序，钻头最佳行进路径是指钻头经过各个钻孔且仅经过一次的最短路线。钻头行进路径包括在同一刀具下打同一批孔的行进路径和进行下一批过孔的打孔时刀具转换时钻头的行进路径。最优刀具转换顺序可通过穷举法得到，在同一刀具打同一批点时钻头的最佳行进路径是一个典型的旅行商问题，属于组合优化的范畴，可利用现在优化算法进行求解。通过对模拟退火法，遗传算法和蚁群算法这三种现代优化算法的优化效果进行比较发现蚁群算法的优化效果更好，所以本文采用蚁群算法对钻头行进路径进行优化。问题一分析：由于一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。所以可以把每个刀具需要打的点操作完毕后再转换到下一个刀具，如d刀具，需要打D、G两类孔型，则可先用d刀具将D,G两类孔型打完再转换刀具。这样就可以大大的减少刀具转换次数，从而减少刀具转换所用的时间。这就需要对刀具的转换顺序进行优化，以达到刀具转换所用时间最短的目的。 因为钻头的行进速度是一定的，所以钻头的行进时间是由钻头的行进路径长短决定的。所以对同一刀具所打的孔，要找出钻头行进的最短路线，这属于典型的旅行商问题，可利用模拟退火法，遗传算法，蚁群算法等现代优化算法进行求解。由于本题的数据比较小，而蚁群算法又具有局部搜索速度快、收敛性良好的优点，所以本文采用蚁群算法对本问题的最优线路和最短路径进行求解，用模拟退火法，遗传算法对蚁群算法进行优化和检验。问题二分析：对于双钻头打孔机，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距），将电路板分成三个区域。具体分区方法是，在左右两侧1.5cm处（即处）分别作x轴垂线即可将电路板分成三个区域，即的一区， 的二区和的三区（如图5-6所示）。则一区和三区内的点都不小于3cm，所以可以使两个钻头分别在一区和三区同时打孔，这样就节省了打孔时间。两钻头打孔时刀具的转换顺序不变，打孔路径为由问题一的蚁群算法确定的最优路径。当一、三区的孔都打完后再打二区的孔。对于二区，则采用两个钻头交替打孔的方式，在一个钻头打孔时，另一个钻头按照刀具转换顺序转换刀具，前一个刀具打完空后，下一个刀具继续打孔，如此交替操作，这样就节省了刀具转换的时间。然后求解出此方案下的钻头行进时间和作业成本等与问题一进行对比。对比后发现此方案虽然使用了双钻头同时打孔，但并未提高打孔机的生产效能，所以又提出了双钻头交替打孔的方案。双钻头交替打孔是指一个钻头打孔的同时另一个钻头按已知刀具转换顺序转换到下一刀具，待上一刀具打孔完后，下一钻头直接打孔，如此循环操作，直到将空打完。这样可以节省一部分加工时间，提高打孔机的生产效能。三、模型假设（1）假设对于同一孔型钻孔作业时间都是相同的；（2）假设钻头为一质点；（3）假设刀具的转换与钻头的行进是两个独立的运动过程，互不影响；（4）假设钻头的行进速度是相同的，刀具在行进中可以同时进行刀具转换，但相应费用不减；（5）假设一块线路板上的过孔全部加工完成后再制作另一块线路板；（6）在同一线路板上的孔不要求加工完毕一个孔，再加工另一个孔，即对于需用两种以上刀具加工的过孔，只需保证所需刀具的加工次序正确即可。四、符号说明 ：钻头行进成本（元/mm）； ：刀具转换的时间成本（元/s）； ：钻头行进速度（mm/s）； ：钻头行进总线路长； ：分别表示刀具打孔时钻头行进的最短路线长（mm）； ：对于转换刀具时从一种刀具打出的最后一个点与下一个刀具的第一个点距离总长度。 ：对于刀具转换时从一种刀具打出的最后一个点与下一个刀具的第一点的距离； ：加工总费用（元）； ：刀具转换费用（元）； ：钻头行进费用（元）； ：相邻两刀具的转换时间（s）； ：一，二区打孔完成时所用时间； ：三区打孔所用时间； ：按照最优刀具转换顺序转换刀具所转过刀具的个数； ：打孔机加工时转换刀具的次数； ：刀具转换次数； ：打孔机工作的总时间（s）； ：刀具转换所用的时间（s）； ：钻头行进所用的时间（s）。五、模型的建立与求解由以上分析可知，打孔机的生产效能主要取决于刀具的转换时间和钻头的行进时间，刀具的转换时间可以通过对刀具转换顺序的优化来缩短，钻头行进时间可以通过钻头行进路径的优化来缩短。建立以总加工费用最少为优化目标的函数：。要使总加工费用达到最少，则刀具转换费和钻头行进费均达到最小。其中刀具转换费：，钻头行进费：。5.1 问题一模型的建立及求解5.1.1 模型的建立 刀具转换费，其中，则； 钻头行进费 ，其中，则；则总加工费 。 5.1.2 模型的求解 首先通过穷举法确定了刀具的最优转换顺序为：。刀具转换费用为，其中，则然后在已知最优刀具转换顺序的前提下，利用蚁群法对于钻头行进路径进行优化。已经确定刀具的最优转换顺序为：。打孔机工作时，每个刀具将需要打的点操作完毕后在转换到下一个道具，如d刀具，需要打D,G两类孔型，将这两类的点的坐标集合在一起，然后放入蚁群算法中的城市坐标，在matlab中运行得出最优路径和最短路线，再转到c刀具进行相同操作，依次按最优刀具转换顺序转换刀具运行以上操作。5.1.2.1蚁群算法的基本思想研究表明,蚂蚁具有找到蚁巢与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的。蚂蚁在一条路上前进时，会留下挥发性信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。对于一条路径,选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈。通过这种正反馈，蚂蚁最终可以发现最短路径。5.1.2.2蚁群算法解决TSP问题的基本原理设整个蚂蚁群体中蚂蚁的数量为m,孔型城市的数量为n，城市i与城市j之间的距离为（i，j=1,2，n），t时刻城市i与城市j连接路径上是信息素浓度为。初始时刻，各个城市之间连接路径上的信息素浓度相同，不妨设为。蚂蚁k（k=1,2，m）根据各个城市间连接路径上的信息素浓度决定其下一个访问的城市，设表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为： 其中，为启发函数，1/,表示蚂蚁从城市i转移到城市j的期望程度；allow(k=1,2,，m)为蚂蚁k待访问的城市的集合，开始时，allow中有（n-1）个元素，即包括除了蚂蚁k出发城市的其他所有城市，随着时间的推经，aollw，中元素不断减少，直至为空，即表示所有的城市均访问完毕，为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率移到距离最短的城市。如前文所述，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素逐渐消失，设参数表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环以后，各个城市间连接路径上的信息素浓度需要进行实时更新，即其中，表示第k只蚂蚁在城市i与城市j连接路径上释放是信息素浓度；表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。针对蚂蚁释放信息素问题，采用 ant cycle system模型。ant cycle system模型中，的计算公式如下：5.1.2.3蚁群算法解决TSP问题的基本步骤基于上述原理，将蚁群算法应用于解决TSP问题一般需要以下几个步骤，其流程图如图51所示。当前迭代次数加1清空路径记录表N达到最大迭代次数？ 输出最优解更新信息素构建解空间初始化参数 Y开始结束图 51 蚁群算法解决TSP的流程图5.1.2.4 钻头最佳路径的求解 利用matlab7.8编程得到用蚁群法解决TSP问题的程序（程序见附件2），将同种刀具所打得点坐标集合到一起，然后放入蚁群算法中城市坐标，在matlab7.8中运行得出最优路径和最短路线。运行后的结果为（这里仅以e，g刀具为例）： 图52 e刀具最优路线 图53 e刀具最短距离与平均距离的对比图备注：【e刀具的具体路径坐标编号见附件3。】图54 g刀具最优路线图55 g刀具最短距离与平均距离的对比图备注：【g刀具的具体路径坐标编号见附件4。】 表5-1 最终最优路径运行结果（单位:1/100mil）刀具dcbah最短距离()5.8532e+0063.7642e+0061.1300e+0071.2277e+0072.6547e+006刀具gf ec最短距离()2.5743e+0066.9258e+0065.8611e+0068.9772e+006表5-2 一种刀具打的最后一点到下一刀具打的第一点钻头行进线路长（单位：1/100mil）刀具转换线路长（）6.5143e+0052.9819e+0052.8218e+0053.2730e+005刀具转换线路长（）8.3768e+0055.0767e+0053.4227e+0055.7055e+005根据以上的运行结果，经计算的：则， 则总加工费用为钻头行进时间总时间5.1.3 模型的检验由于掌握到解决TSP的方法不止蚁群算法，综合考虑本文又采用了遗传算法和模拟退火算法对最优路径进行计算对比，结果如下：表 5-3 蚁群算法、模拟退火算法、遗传算法结果对比蚁群算法（单位:1/100mil）刀具dcbah最短距离6004513.21673842679.112911326131.528312495638.49443087550.1457刀具gfec最短距离3221084.95577124864.29745987212.35429120042.9394模拟退火算法（单位:1/100mil）刀具dcbah最短距离31192739.93019545734.6614102478444.1079108856983.74765156597.5294刀具gfec最短距离5469036.81919414918.800325771283.976243037354.7943遗传算法（单位:1/100mil）刀具dcbah最短距离72350681.287114303426.3422232961376.057218205319.43083130271.5002刀具gfec最短距离3872153.555236417401.06864739607.370198969885.9004结合以上对比结果可以得出最优算法是蚁群算法。对于转换刀具时从一类刀具打出的最后一个点与下一个刀具的第一个点的距离可能不是最优路径，但是考虑同一刀具路径最优为首要因素，此处误差较小，暂不予考虑。5.2 问题二模型的建立与求解5.2.1 模型的建立模型一：分区域双钻头同时打孔首先将整个电路板区域划分成三个部分，划分方法：在左右两侧1.5cm处（即处）分别作x轴垂线即可将电路板分成三个区域，即的一区， 的二区和的三区。划分结果如下图所示： 图5-6 电路板区域划分图（1）对于单个区域刀具转换费，其中，则； 钻头行进费 ，其中，则；则总加工费 。 （2）对于一，二，三区一，二区打孔所用的时间 其中 三区双钻头交替打孔打孔所用时间 则总加工时间 一区总费用 二区总费用 三区总费用 全部费用 模型二：双钻头交替打孔 总费用 总加工时间 5.2.2 模型的求解与结果 模型一的求解 将三个区域的孔坐标用问题一的方法，将其坐标的集合放入蚁群算法的城市坐标中，在matlab7.8中运行蚁群算法程序得到如下结果：表5-4 区域一刀具运行最短距离（单位：1/100mil）刀具dcbah刀具运行最短距离（）2.7543e+0068.2962e+0055.5840e+0065.2295e+0065.7399e+005刀具gfec刀具运行最短距离（）3.4654e+0052.1841e+0062.4339e+0062.9921e+006表5-5 区域二刀具运行最短距离（单位：1/100mil）刀具dcbah刀具运行最短距离（）2.8607e+0062.3409e+0064.0587e+0065.6808e+0061.3632e+006刀具gfec刀具运行最短距离（）1.4386e+0063.3369e+0063.4529e+0064.2546e+006表5-6 区域三刀具运行最短距离（单位：1/100mil）刀具dcbah刀具运行最短距离（）2.0885e+0051.1563e+0061.7446e+0063.1707e+0065.8653e+005刀具gfec刀具运行最短距离（）3.6056e+0051.4982e+0062.3227e+0051.6447e+006表5-7 区域一转换刀具时钻头行进线路长（单位：1/100mil）刀具转换线路长（）4.1141e+0051.3142e+0053.4640e+0053.8236e+005刀具转换线路长（）4.5390e+0055.1143e+0057.3059e+0057.1420e+005表5-8 区域二转换刀具时钻头行进线路长（单位：1/100mil）刀具转换线路长（）6.3683e+0054.0860e+0057.0196e+0055.4665e+005刀具转换线路长（）2.3454e+0052.4526e+0052.0883e+0046.8349e+005 表5-9 区域二转换刀具时钻头行进线路长（单位：1/100mil）刀具转换线路长（）3.2404e+0053.6734e+0051.8357e+0054.5171e+005刀具转换线路长（）01.6999e+0055.7030e+0051.2772e+005根据以上的运行结果，经计算的：（1） 当两个钻头同时打孔时 对于区域一则， 则总加工费用为钻头行进时间总时间 对于区域二则， 则总加工费用为钻头行进时间总时间 对于区域三则， 则总加工费用为钻头行进时间因为远小于，且双钻头交替打孔时，可认为钻头一边打孔一边转换刀具则总时间综上可得：双钻头打区域一，二的时间 双钻头交替打区域三的时间 总时间总加工费用模型二的求解：当进行双钻头交替打孔时，由于两个钻头都进行了刀具转换，所以刀具转换费用应包括两个部分，而钻头行进费用则与问题一相同。总费用其中 则（注：其中未考虑钻头替换时，钻头的行进线路长）总加工时间其中 则5.3 结果的比较和分析5.3.1 结果的比较（1） 单钻头 总费用 总时间（2） 双钻头 双钻头同时加工 总费用 总时间 双钻头交替加工 总费用 总时间5.3.2 结果的分析由以上结果经比较得出：当双钻头同时加工时相对于单钻头加工过程打孔机的生产效率并没有提高，反而降低了。当双钻头交替加工时则打孔机的生产效能有所提高。5.4 打孔机的两钻头合作间距对作业路线和生产效能影响的分析通过计算结果显示打孔机的两钻头为避免钻头间的触碰和干扰，