2012深圳数学建模夏令营打孔机生产效能的提高论文

《2012深圳数学建模夏令营打孔机生产效能的提高论文》由会员分享，可在线阅读，更多相关《2012深圳数学建模夏令营打孔机生产效能的提高论文（29页珍藏版）》请在金锄头文库上搜索。

1、考虑问题思路较开放，方法合理，写作较好。建议部分图可放到附考虑问题思路较开放，方法合理，写作较好。建议部分图可放到附录里。优录里。优打孔机生产效能提高的建模分析打孔机生产效能提高的建模分析摘 要：在电子行业市场飞速发展的今天，集成度超高的电路板是各种电子产品不 可或缺的一部分，本文针对生产线上印刷电路板过孔的生产效益的提高进行了 深入的研究，通过使用枚举法和蚁群算法，得出刀具在电路板上打孔作业的最 优化作业线路，提高了打孔机的生产效能。 对于问题一，通过对成本进行评估分析，我们认为打孔机在单刀具打完整 块电路板后再换刀的成本是最低的，而且节省了频繁换刀的时间，效率也相应 地提高了。由题可知，在

2、加工作业时，打孔机单个钻孔的作业时间，钻头的行 进时间以及刀具的转换时间是影响生产效益的三个重要因素。在走刀打孔时， 钻头行进的时间以及刀具转换的时间越短，生产效益越高。且钻头行进的总时 间由钻头行进路线决定， 而刀具转换总时间根据所制定的最低成本方案决定。 我们用枚举法的方式列出了最低成本的换刀顺序，其次再用蚁群算法模拟出每 次走刀时最短作业线路，最后根据单位换刀成本及单位走刀路线成本计算出总 费用的表达式。 对于问题二，打孔机由单钻头设计成双钻头时，根据题目已知得到，作业 时各钻头是相互独立工作的，这里主要解决的问题是如何在打孔走刀时始终保 持两钻头间的合作间距在安全距离 3cm 以上，分

3、析得出合作间距对作业路线和 生产效能产生的影响。针对以上所述双钻头的工作特点，我们制定第一套作业 方案：两钻头不同时钻孔，在一个钻头作业时，另一个钻头切换刀具或者等待。 这样钻头间就不存在合作间距的问题了，利用蚁群算法计算最短路径，且经过 计算得出，在费用成本基本不变的基础上降低了时间成本。针对问题二，我们还尝试制定了第二套作业方案，以循环作业的方式来保 证两个钻头的合作工作间距在 3cm 以上，电路板划分为三个区域，中间 3cm 宽 度的区域用于保证两个钻头打孔的时候间距达到 3cm 以上。在这套方案中，利 用蚁群算法分别对三个区域内各个刀具的路径进行计算，得出最短路径，然后 与单刀的考虑方

4、式相同，用枚举的方式制定两个钻头上刀具的优先顺序，这种 方案作为一种求解钻头的安全作业间距对生产性能的影响的方法，在符合基本 条件的基础上，既考虑到了时间成本，又兼顾了费用成本。关键词：关键词： 生产效率；蚁群算法；TSP 问题；双目标优化 队员：谢林利；刘超；殷国亮一、问题重述过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加 工费用通常占制板费用的 30%到 40%，打孔机主要用于在制造印刷线路板流程中 的打孔作业。本问题旨在提高某类打孔机的生产效能。 打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间， 这是由生产工艺决定，为了简化问题，这里假定对于同一孔型

5、钻孔作业时间都 是相同的；（2）打孔机在加工作业时，钻头的行进时间；（3）针对不同孔型 加工作业时，刀具的转换时间。目前，实际采用的打孔机普遍是单钻头作业， 即一个钻头进行打孔。 现有某种钻头，上面装有 8 种刀具 a，b，c， , h，依次排列呈圆环状， 如图 1 所示。bcdefgha图 1：某种钻头上 8 种刀具的分布情况 而且 8 种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后， 可以转换使用另一种刀具，相邻两刀具的转换时间是 18 s。例如，由刀具 a 转 换到刀具 b 所用的时间是 18s，其他情况以此类推。作业时，可以采用顺时针 旋转的方式转换刀具，例如，从刀具 a

6、 转换到刀具 b；也可以采用逆时针的方 式转换刀具，例如，从刀具 a 转换到刀具 h。将任一刀具转换至其它刀具处， 所需时间是相应转换时间的累加，例如，从刀具 a 转换到刀具 c，所需的时间 是 36s（采用顺时针方式） 。为了简化问题，假定钻头的行进速度是相同的，为 180 mm/s，行进成本为 0.06 元/mm，刀具转换的时间成本为 7 元/min。刀具在 行进过程中可以同时进行刀具转换，但相应费用不减。 不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型 A 只 用到刀具 a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型 C 需要 刀具 a 和刀具 c，且加工次序为 a

7、，c。表 1 列出了 10 种孔型所需加工刀具及加 工次序（标*者表示该孔型对刀具加工次序没有限制） 。 表 1：10 种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, c d, e* c, f g, h*d, g, fhe, cf, c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路 板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种 以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。 请建立相应的数学模型，并完成以下问题： （1）附件 1 提供了某块印刷线路板过孔中心坐标的数据，单位是 1/100 密 尔（mil） （也称为毫英寸，

8、1 inch=1000 mil） ，请给出单钻头作业的最优作业 线路（包括刀具转换方案） 、行进时间和作业成本。 （2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状 与单钻头相同） ，两钻头可以同时作业，且作业是独立的，即可以两个钻头同时 进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间 的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于 3cm（称为 两钻头合作间距） 。为使问题简化，可以将钻头看作质点。 （i）针对附件 1 的数据，给出双钻头作业时的最优作业线路、行进时间和 作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？ （ii）研

9、究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。二、问题分析本文主要解决打孔机给电路板钻孔的生产效能提高的问题，即成本低、时 间短。由于单个过孔的钻孔作业时间是由生产工艺决定的，而且题目中未给出 钻孔的单位成本，所以为了简化问题，不考虑总时间中钻孔所需的时间。那么 为达到目标，我们跟据题意主要从剩余的两个方面考虑问题：1、怎样制定最短 路径，使打孔机在加工作业时的走刀时间达到最小；2、怎样制定最优的转换顺 序，使得在连续加工不同孔型时，刀具的转换时间达到最小值。 2.12.1 问题一分析问题一分析 对于问题一，首先我们制定出两种作业方案：（1）以数量多的孔型 A、B、C、D、E 的坐标

10、为主，根据刀具打孔的优先级顺序，制定这些孔的单次 走刀顺序，然后在走刀时遇到数量小的孔型 F、G、H、I、J 坐标时，及时换刀 对其钻孔，省去了为小数量的孔型专门走一次刀而花费的成本；（2）直接根据 刀具的优先顺序，按序钻孔，虽然需要对数量小的孔型也要专门走刀，但是大 大地节省了刀具的转换时间及成本。经过数据分析，比较得出方案 2 作为问题 一的最优作业路线。 根据方案 2 叙述，接下来开始寻找刀具切换的优先顺序，使刀具转换成本 达到最低，我们使用枚举法的方式最后选到的一组最优顺序为：d-c-b-a- h-g-f-e-c。 其次再用蚁群算法模拟出每次走刀时最短作业线路，要给出最优作业方案， 就

11、要使总加工费用最小。由于单个过孔的钻孔作业时间是由生产工艺决定的， 所以最优作业的方案就由钻头的行进时间和刀具的转换时间两个因素决定，通 过蚁群算法计算达到加工总费用越小，每个刀具的作业路线最优。最后根据单 位换刀成本及单位走刀路线成本计算出总费用的表达式。 2.22.2 问题二分析问题二分析 问题二旨在解决打孔机由单钻头变为双钻头时，如何协调两钻头间的工作 关系。因为作业时各钻头相互独立，且有合作间距的限制，因此在解决双钻头 最优作业方案时，我们考虑一种极限情况：两钻头不同时钻孔，在一个钻头作 业时，另一个钻头切换刀具或者等待。这样钻头间就不存在合作间距的问题了，而且这是基于问题一的一种解法

12、，利用蚁群算法计算最短路径，且经过计算得 出，在费用成本基本不变的基础上降低了时间成本。 在第二套方案中，我们把双钻头的安全工作间距对生产效能的影响加入考 虑，将电路板划分成三块区域，中间区域的宽度为 3cm，双钻头同时在不同区 域打孔，轮换完全区域打孔后，各自以最优换刀顺序同时换刀，继而打下一孔 型。如此循环，直至打完所有孔结束，打孔路径同样由蚁群算法得出。经计算， 同样达到了降低时间和成本的目的。三、问题假设1) 单个过孔的钻孔作业时间，是由生产工艺决定的，这里可以假设对于同一孔 型钻孔作业时间都是相同的； 2) 为了计算行进费用，需要计算行进时间，可以假设打孔机的行进是一个匀速 运动；

13、3) 刀具转换时，无论是在顺时针还是逆时针情况下，每个相邻的刀具间的转换 时间都是相同的； 4) 在计算两孔之间距离时，假设打孔机的钻头看作一个质点；四、符号说明符号名称符号意义 K打孔机加工的总成本 K1钻头行进的成本 K2刀具转换的成本 T打孔机加工的总时间 T1钻头行进的时间 T2刀具转换的时间 M钻头行进的总路程 N刀具总的转换次数 v钻头行进速度 t相邻两刀具的转换时间 a1钻头行进成本 a2刀具转换的时间成本五、模型的建立及求解5.15.1 问题一模型的建立问题一模型的建立 5.1.15.1.1 方案的确定方案的确定 对于方案 1 和方案 2，根据题目以及附件给出的数据，以钻 A

14、型孔和 H 型 孔为例，假设 A 孔有 200 个，H 孔有 20 个，因为从 a 刀具切换到 h 刀具所需的 时间为 18s，且刀具转换的时间成本为 7 元/min，所以可以得到 a 刀具和 h 刀 具间切换一次所需的成本费用为 2.1 元，需 18s。根据附件中的数据经过单位 转换后分析得到，电路板上钻孔的坐标不超过 250*250mm2面积范围，因为钻头 的行进速度是相同的，为 180 mm/s，行进成本为 0.06 元/mm，为简便计算，假 设 H 型孔是面积上以网格形式平均分布的点，如果按方案 2 来计算，其走线的 成本约为 75 元，需 7s 多的时间；如果按方案 1 来算，假设

15、H 型孔在 A 型孔的 行走路线上，在打 A 型孔的时候，遇 H 型孔进行换刀打孔，所花的成本约为 84元，多花了 720s 的时间，所以无论从价格成本还是从时间上看，方案 2 明显比 方案 1 更加优越，所以我们使用方案 2 作为单钻头作业的最优作业线路方案。 5.1.25.1.2 刀具优先顺序的确定刀具优先顺序的确定 根据方案 2 叙述，接下来开始寻找刀具切换的优先顺序，使刀具转换成本 达到最低，我们使用枚举法的方式最后选到的一组最优顺序为：d-c-b-a- h-g-f-e-c。 题中表 1 给出的不同孔型的刀具优先顺序，从表中可以看到 c 刀具和 f 刀 具之间的优先级是既有 cf,又可

16、以 fc，除此之外的刀具均有明确的先后顺序， 所以刀具最少使用 9 次转换，加上从成本最优原则角度考虑，从最少转换次数 出发，我们列出了一下 16 组刀具转换顺序： 1、a-b-c-d-e-f-g-h-c 2、a-h-g-f-e-d-c-b-f 3、b-c-d-e-f-g-h-a-c 4、b-a-h-g-f-e-d-c-f 5、c-d-e-f-g-h-a-b-c 6、c-b-a-h-g-f-e-d-c 7、d-e-f-g-h-a-b-c-f 8、d-c-b-a-h-g-f-e-c 9、e-f-g-h-a-b-c-d-f 10、e-d-c-b-a-h-g-f-c 11、f-g-h-a-b-c-d-e-f 12、f-e-d-c-b-a-h-g-f 13、g-h-a-b-c-d-e-f-c 14、g-f-e-d-c-b-a-