打孔机生产效率全方位提高_数学建模

1、印刷电路板打孔的效能全方位摘 要本文就打孔机生产效能的提高，运用Matlab和穷举法建立数学模型，针对实际问题，分别考虑两条原则：路径和转换方式最优原则，时间最优原则建立模型。由于两个问题都为优化问题，我们用TSP模型求解钻头行进路程的最短路径，以穷举法分析最优刀具转换方式。针对问题一，根据题目提供的印刷线路板过孔中心坐标数据，我们利用Matlab 画出了坐标分布图。分析其点分布，发现dcbahgfec 这种刀具转换方式不仅能保证每个点都打到且转换次数最少，这样就不仅降低了转换成本,而且也使转换时间缩小到最少的。经过我们的反复计算，最终行进总路程为1633.72cm，行进时间为1727.21，

2、作业成本为1001.23元。对于双钻头的打孔机，它的作业是独立的，但为避免钻头间的触碰和干扰，我们采取了分区域的做法，即两个钻头分开作业。根据分析，决定将其分为四个区域并根据各个区域各种孔型分布特点，求出最短刀具转换方式。经过统计和计算，最终行进总路程为1407.86cm，行进时间为1534.32s，作业成本为924.516元。与单钻头比较时间效率提高了552.01s，缩短了钻头的行进路程，成本降低了24.06元。针对问题二，我们对问题一进行了优化，用牺牲刀具的转动时间来做到减短钻头所行总路线，将其划分为四个区域，钻头根据区域依次行走，经过计算得出最终行进总路程为1475.96 cm，行进时间

3、为2086.33s，作业成本为948.58元，相比原本的方法，此种方法虽时间稍微多一些，但钻头行进路程变短了，也降低了成本。关键字：Matlab TSP 穷举法一问题重述打孔机主要用于制造印刷线路板流程中的打孔作业。为提高生产效能，需进行合理的作业安排，设计加工一块线路板的最优计划，需考虑以下几个方面：(1)单个过孔的钻孔作业时间，这是由生产工艺决定；(2)打孔机在加工作业时，钻头的行进时间；(3)针对不同孔型加工作业时，刀具的转换时间。在给定的某种砖头，上面装有8种刀具a,b.c ,h,依次排列呈圆环状，如图 1所示：ahgf e b c d图1：某种钻头8种刀具的分布情况而且8种刀具的顺序

4、固定，不能调换。加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间为18s。作业时，可采用顺（逆）时针旋转的方式转换刀具。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为简化问题，假定钻头的行进速度是相同的，为180mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同刀具加工不同孔型，表一列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。 表1：10种孔型所需加工刀具及加工次序孔型 A B C D E F G H I J 所需刀具 a b a, c

5、 d, e* c, f g, h* d, g, f h e, c f, c同一线路板上的过孔不要求加工完毕一个孔，再加工令一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。要求：根据提供的数据给出单钻头的最优作业线路（包括刀具转换方案）、行进时间和作业成本；(2)设计一种双钻头的打孔机，（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。(i

6、)针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？(ii)研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。三 问题分析3.1 问题1的分析问题1所求的是单钻头作业最优生产效能，本题目要求综合刀具转换方案、行进时间和作业成本给出单钻头作业的最优加工线路。结合附件1给出的数据，我们初步确定用图论中的最短路径进行求解，而求解最短路径的是退火算法。对单钻头作业生产效能的影响因素进行分析，可以得到以下因素：1、每个钻头在印刷电路板的前进时间；2、对于每个钻孔，过孔的钻孔作孔时间；3、对于不同孔型加工作业，刀具的转换时间所消

7、耗的时间。因此，我们对以上三个影响因素进行综合分析，得出两种解决方法：（1）、减少钻头的转换时间；（2）、减少钻头的前进时间，即找到各钻头在钻头前进的最短路径。考虑到钻孔类型和钻头的种类不是一一对应的，因此，我们先确定刀具的最短转换顺序，然后再对应每一个刀具分别分析钻孔的最短路径。对于刀具的最短转换顺序，在考虑十种刀具所对应的孔型顺序时，我们利用枚举法进行求解，以得到最优的孔型顺序。在对每一个刀具进行最短路径的分析时，我们利用最优化问题的普遍求解算法模拟退火算法进行求解，从而对最有生产效能下最优化路线进行分析和求解。3.1 问题2分析问题2将情况分为双钻头情况下的打孔机工作，要求求解最高生产效

8、能以及工作效率的提高率。在求解最高生产效能问题中，我们沿用了问题1的思路，采用区域的思想，按照孔型分布情况将线路分为四个区域，再分别对每一个区域确定刀具的转换方式和打孔顺序，然后综合考虑两组钻头打孔的时间和费用，再进行调整，以此找出最优路径图。此外，我们还可以考虑“磨刀不误砍柴工”的思想，使得钻头1在线路板上行进时候钻头2在转换刀具，待钻头2转换刀具结束开始进入线路板进行打孔，钻头1退出线路板3cm，以此往复。最终我们拿两种求解结果进行比较，以获得最优的工作效能。五、模型的建立于求解（1）刀具的最佳转换方案因为道具可以有顺时针旋转和逆时针旋转，通过穷举法得到全部方案： 方案1：abcdefgh

9、gfedc 方案2：ahgfedcbahgf 方案3：bahgfedcbahgf 方案4：cdefghabcdef 方案5：cbahgfedcbahgf方案6：defghabcdef方案7：dcbahgfedcbahgf 方案8：dcbahgfec方案9：efghabcdefgf方案10：edcbahgfedc方案11：fghabcdefghedc 方案12：fedcbahgfedc方案13：ghabcdefgfedc方案14：gfedcbahgfedc方案15：habcdefghedc方案16：hgfedcbahgfedc通过分析各方案的转换次数可以发现，最佳的刀具转换方案，也就是转换次数最

10、小的方案，是方案8：dcbahgfedc。根据方案8，可以求得每种刀具所能打的孔型的最佳方案。针对方案8，每次转化钻头所需打的孔型见表1：表1钻头对应的钻孔孔型序列步骤 刀具 每一步对应刀具所能打的孔型d D、G 1c 2 E3 b Ba 4 A、Ch F、H 5g 6 F、G7 f G、J、Ee 8 I、D9 c C、J、I（2）线路板钻孔分布对于问题一，我们首先做出钻孔在线路板的分布情况，如图1所示图1 线路板钻孔分布图（3）最优路径模型通过穷举法，我们得到了刀具转化的最优方案。我们把孔中心看做城市，钻头看做商人，那么钻头打好一种孔型就如同商人遍访每一个城市，商人行进路程S即为钻头的作业距

11、离。若问题的解空间M可表示为1,2, ,n的所有排列的集合，即M=(c1,c2, ,cn)|(c1,c2, ,cn)为1,2, ,n的排列其中，每个排列Mi表示遍访n个城市的一个路径，ci=j表示第i次访问城市j。 原始数据矩阵为coorn3(NXY)N为城市编号，X为城市的x轴坐标，Y为城市的y轴坐标。那么coor_x=coorn3(Ncoor_y=coorn3(NXXY)(010) Y)(001)即可得到原始数据矩阵的x坐标，y轴坐标。要算出每个点和其他所有点的距离，需要将coor_x，coor_y延拓成n阶方阵，定义一个n阶方阵On：1 1On= 1 1nncoor_xnn=coorn3

12、(Ncoor_ynn=coorn3(NXXY)(010)OnY)(001)On应为要通过向量化的方法计算距离矩阵，所以要进行转置记为：TT,coor_xncoor_ynnn于是有i城市到j城市的距离矩阵：Dij=ij那么我们可以得到一个访问所有城市的路径总长度：S=i、jDD通过模拟退火算法得到函数C的一个最优值。下面我们以孔型G和刀具g为例进行说明，虽然钻孔型G时，要用到d、g、f三种刀具，在这里我们只选取打孔型G时，使用刀具g这一步骤。在附录中我们可以得到孔型G的中心坐标数据，将它编号如下表2：表2 孔型G的中心坐标1 2 3 4 5 6 7 8 9 10X -301300 -301300

13、 -301300 -301300 -301300 -301300 -301300 -301300 -321300 -321300Y -19200 23400 -42400 43400 -62400 64300 800 84300 -19200 2340011 12 13 14 15 16 17 18 19 20X -321300 -321300 -321300 -321300 -321300 -321300 153000 173000 193000 213000Y -42400 43400 -62400 64300 800 84300 892600 892600 892600 892600根据

14、模型我们得到Dij这一个距离矩阵表3 Dij矩阵里的数据表（105 mil）1 2 1 0 0.4260 2 0.4260 0 20 5.2461 5.1789 .在这里i=20，j=20。由于数据太多，就不在具体写出矩阵Dij中数据时每个点和其他的所有点的距离即关系矩阵。对角线上，因为是各点到自己本身的距离，所以值为0。然后第一行表示点1到其他各点的距离，如点1到2点的距离是0.4260×105 mil.第一列表示各点到点1的距离，如点20到点1的距离是5.2461×105 mil.进而我们得到我们的目标函数，假设S为总的距离。开始按照原始数据的路径来行进,即顺序1,2,

15、3,20。我们将这个顺序集合表示为:D=1,2,20 目标函数是这个总的距离达到最小值即：minS=i、jDDi=(1,2, ,20),j=(1,2, ,20) ij下面我们通过随机选择两个点或三个点，交换他们的顺序，得到一个新解记为长度S,比较S和S的大小，将小的程度保留。然后继续进行随机选取点和求总长度，比较得较小者。经过多次的随机选择，得到最优的即最小的总长度并记录最优的路径。这样就得到了最短路径通过上面的模型我们得到了在打G孔型时g刀具的最优路径及最短距离。 最优路径：1353172417181920816146121015911最短距离：2.3017e+006由图2可以看出，使用退火

16、算法模拟最优路径，很好地求解了钻头打孔的最短路径，使得个坐标点之间距离最优化，最后结果得到的路径长度比较满意。路径图2：图2 “g”钻头最优打孔路线图通过以上对“f”钻头的分析与求解，我们采用相同的方法对九个序列分别进行求解，可得各钻头在线路板上最短路径如表4所示。钻头 d c b a h g f e c起点坐标 -27400,54100 126200,845600 -88200，370000 -54200,205000 -311300，-52400 -301300，-62400 -321300,64300 -2900，54100 -65800,473600终点坐标 -17400,54100

17、106800,837200 -61800,390400 -6400，221600 69000，-1800 -311300,74300 -321300,43400 235855,832162 -65400,473600长度 6.20751064.1457106 2.7888107 3.1590107 3.1144106 3.2252106 7.4588106 6.5305106 1.2341107通过上表的起点和终点坐标，可以求出刀具转换过程中路径长度，如表5所示表5 单钻头下刀具转换过程中的移动路径长度（mil）起点终点dc cb ba ah hg起点坐标 -17400,54100 10680

18、0,837200 -61800,390400 -6400，221600 69000，-1800 -311300,74300 -321300,43400 235855,832162终点坐标 126200,845600 -88200，370000 -54200,205000 -311300，-52400 -301300，-62400 -321300,64300 -2900，54100 -65800,473600移动路径长度8.0442105 5.0626105 6.0615105 4.0993105 3.7523105 1.4142104 3.1858105 4.6857105gffeec通过表2

19、中数据我们可以得到，各钻头在线路板上最优总路径长度（单位：mil）为：S=si=42.282106(mil)（4）单钻钻头打孔费用、作业时间及作业成本通过以上对模型的分析，可以得到最优作业线路下行进时间的关系表达式为：T=Tk+Ti,j其中Tk代表最优作业线路下刀具行进的总时间，Ti,j代表最优作业线路下刀具从i转换到j所消耗的时间由于刀具行进总时间可由总路径长度S求得，因此，我们接下来对刀具转换时间进行考虑，刀具转换的时间为18s，大部分的刀具转换都在移动路径中转换好了，除去gf，它的移动路径中所需时间小于刀具转换时间，那么将他记为18s。最后得出总时间T=Tk+Ti,j=6814s2、单钻

20、头打孔机在线路板最优费用求解通过对题目的分析，可以得出作业成本的关系式如下：W=W1(i,j)+W2(k)+Q(k)其中，（单位：元）；W1(i,j)代表钻头从i钻头转换到j钻头所需的费用W2(k)代表第k个钻头在线路板上前进的总费用；Q(k)表示钻头转换所需要的费用（单位：元）。在模型2对钻头模型分析可知，W1(i,j)=T(i,j)s其中，T(i,j)代表从i钻头转换到j钻头所需要的时间（单位：秒）；s代表刀具转换的时间成本（单位：元）。因此，钻头转换过程中前进所需的费用（单位：元）为：Q(k)=S总t行钻头转换过程中转换所需要的费用（单位：元）为：W1(i，j)=T(i,j)s所以，最后

21、所需的费用（单位：元）为：W=W1(i,j)+W2(k)+Q(k)=64416（元）5.2问题二的求解双钻头作业的最优生产效应分析1研究双钻头协同工作时对线路板区域的分块在考虑双钻头协同工作的模型时，由于两个钻头同时工作，且相距不小于3cm，因此，我们考虑将22.8m×30.48m线路板分成四块，换分区域的要求考虑如下：1、在任何情况下都要满足两钻头直接的距离小于3cm；2、考虑四个区域钻孔密集程度相当；3、考虑双钻头工作时转换区域时候时间相对较短。因此，我们综合考虑上述情况，最终得到处理分块方式如图3所示：图3 双钻头作业时区域分块图上图三条线分别代表的直线方程是：x=-2105,

22、x=0.8105,y=6105。 （2）双钻头作业时线路板各区域钻孔路径分析对于区域1，我们依然采用问题一的方法对其进行研究。其刀具的最短转换顺序仍为：edcbahgfedc,因此，我们使用模拟退火算法对区域1的孔型进行最短路径求解，可得各钻孔行进时的最短路径如表6所示：表6 双钻头作业时区域1各钻头行进最短路径钻头 d c b a h g f e c起点坐标 -220525,556200 -244200,278000 -249800,758600 -244400,258600 -311300,-52400 -301300,84300 -268400,-65200 -276996,259221

23、 -309800,908000终点坐标 -301300,43400 -271900,426500 -215000,-27200 -298800,919000 -319400,456500 -321300,-42400 -298800,908000 -220525,556200 -279400,-65200路径长度 1.584×104 1.494×106 5.090×105 3.401×105 2.310×105 1.862×106 1.640×106 2112×106 1.643×106由上表可得区域1的

24、最短行进长度为S1=1.141072、区域1在最优化效应下最短时间求解由各钻头前进最短路径数据，可以得到区域1打孔路径示意图4图4 分块后区域1最优化路线示意图由此，我们对区域1钻头转换过程中的路径长度进行求解，可以得到数据表7所示：表7 区域1刀具转换过程中的路径长度起点终点 起点坐标 终点坐标 路径长度 dc -301300,43400 -244200,278000 2.41×105 cb -271900,426500 -249800,758600 3.32×105 ba -215000,-27200 -244400,258600 2.87×105 ah -2

25、98800,919000 -311300,-52400 9.71×105 hg -319400,456500 -301300,84300 3.73×105 gf -321300,-42400 -268400,-65200 5.76×104 fe -298800,908000 -276996,259221 9.71×105 ec -220525,556200 -309800,908000 3.63×105 由上表可以得出区域1早刀具转换中行进的距离为2.93×106mil 综上在区域1中作业过程中花费的是时间T1为：T1=t1-1+t1

26、-2其中，t1-1代表区域1中钻头行进所消耗的时间，t1-2代表区域1中钻头转换时消耗的时间。t1-1=S1v综上，可一得到区域1作业过程中花费的时间T1=1806 3、区域1在最优生产效应下费用求解由于区域1沿用问题1中的求解方法，因此把数据带入W=W1(i,j)+W2(k)+Q(k)=19561（3）区域2、3和4最优化路径分析通过上述区域1的分析，我们采用相同的思路对区域2、3和4进行分析求解，最终获得处理数据和结果如下所示：表8 双钻头作业时区域2各钻头行进最短路径钻头 d c b a h g f e c起点坐标 22500,662300 30200,720200 -600,81220

27、0 -38800,648800 4980,706900 -4980,706900 193000,892600 -225600,662300 27800,659800终点坐标 312200,898200 137000,899400 92300,816300 447700,896900 29780,892600 21300,892600 447700,907900 489989,612870 489989,611870路径长度 1.18×106 8.08×105 7.01×105 1.32×106 4.90×105 6.29×105 1.

28、53×106 1.52×106 1.76×106钻头b a h gf e d c表9 双钻头作业时区域3钻头行进最短路径 起点坐标 终点坐标 长度 66118,111992 -5400,469200 8.28×10 -136600，-52800 39300,449800 6.67×106 22800,84200 35200,485800 4.34×106 69000，-1800 -5285,525900 5.51×105 69000，-1800 69000,60700 6.25×104 62600,15800 -5

29、400,469200 1.13×106 53200,60800 -182000,321049 5.92×105 -182000,321049 53200,60800 5.92×105 -60600,41400 35200,485800 1.72×106 表10 双钻头作业时区域4各钻头行进最短路径 起点坐标 终点坐标 长度 332900,2800 169000,417000 9.91×10 143000,16600 114600,45400 2.30×105 220400，-30500 169100,545400 3.05×

30、106 226953,133142 203331,125268 2.01×106 165000，-1200 177500,61300 5.09×105 165000，-1800 81500,60700 2.80×105 100447,511188 219600,28400 1.52×106钻头dc b a h gfc317000,217200 340400，-542001.65×106起点终点dc cb ba ah hg gf fe ec表11 区域2刀具转换过程中的路径长度 起点坐标 终点坐标 312200,898200 30200,7202

31、00 137000,899400 -600,812200 92300,816300 -38800,648800 447700,896900 4980,706900 29780,787100 4980,706900 21300,892600 193000,892600 447700,907900 -225600,662300 489989,612870 -27800,659800路径长度 3.68×101.63×105 5.15×105 4.82×105 8.03×104 1.72×105 7.17×105 2.85×

32、;105起点终点dc cb ba ah ag gf fe ec表13 区域4刀具转换过程中的路径长度 起点坐标 终点坐标 16900,0,417000 143000,16600 114600,45400 220400，-30500 169100,545400 226953,133142 20333,1,125268 165000，-1200 177500,61300 106500-1800 81500,60700 100447,511188 219600,28400 293800，-50200 169000,417000 317000,217200路径长度 4.01×101.30&#

33、215;105 4.16×105 1.32×105 9.50×105 4.51×105 1.08×105 2.49×1052.区域2、3和4最优化路径分析通过表9-表14，可以得到区域2、3、4刀具转换的路径长度和行进的路径长度关系如下表：表14 各区域刀具行进和转换路径长度表汇总区域序号 区域2 区域3 区域4刀具转换的路径长度 4.43×10 2.38×10 1.98×10 行进的路径长度 9.95×106 1.69×106 1.15×106由表 可知，打孔机在区域2、3

34、、4分别打孔所需的时间为：T2=t2-1+t2-2=2089T3=t3-1+t3-2=2813T4=t4-1+t4-2=1957打孔机在区域2、3、4分别打孔所需的费用（单位：元）为：W2=w1(i,j)+w2(k)+q(k)=21961W3=w1(i,j)+w2(k)+q(k)=29508W4=w1(i,j)+w2(k)+q(k)=261243.双钻头下四区域转换方案分析通过对双钻头下刀具转换时间T1、T2、T3和T4的分析，综合考虑划区域的要求，最终我们选择一开始在区域1和区域4两钻头协同工作，接下来通过各区域转换钻头的起点和终点，对区域1、4转换区域的方案进行分析，得到各区域起终点关系如

35、下：表15 区域转换方案分析区域转换方案 钻头行进路径长度（单位：mil）区域1区域2 5.89×10区域4区域3 2.80×105区域1区域3 8.80×105区域4区域2 6.19×105通过表 的分析，我们得出双钻头下区域选取方案为：区域1区域2和区域4区域3。接下来，我们对此方案下的生产效能进行分析。4、双钻头四区域模型下生产效能计算通过以上的分析，可得转换后总时间为：T'=8865最后的费用为W'=1169475.2.3.双钻头四区域模型的评价首先，我们对题意进行了详细分析，得出了双钻头行进路线下对钻头进行的要求，然后，为满足双

36、钻头直接距离不小于3cm我们采用了分区域模型，通过分别对各区域钻孔数据采用模拟退火算法，求出各个区域钻头行进的时间以及费用，最后得出钻换后的时间为T=8865费用为W=116947通过与但钻头结果的对比，发现T>T，W>W ，得出双钻头四区域模型并不能很好地处理双钻头问题，分析原因，归结于各钻头转换所需要的时间太长（18s），而四区域模型对双钻头的转换时间要求比较高，因此，我们接下来基于双钻头四区域模型的思想对该模型进行改进，即减少钻头转换的次数，最终以获得更优化的生产效能。5.2.4.模型3：双钻头工作下最优化效能处理模型1.模型3的建立由双钻头钻孔下四区域分块模型不能很好地解决

37、工作的最优化问题，因此，接下来我们考虑线路板整体分析，最终采用如下思路进行模型搭建：首先考虑双钻头打孔机下如何合理利用两个钻头协同使得工作效率进一步提高，我们考虑采用双钻头分别独立工作的思路，即钻头1在线路板上行进的时候钻头2在转换道具，待钻头2转换道具结束开始进入线路板进行打孔，带钻头1打孔结束退出线路板处3cm，钻头2进入线路板，以此往复。最后对表1分析得到道具加工序列（假设两钻头分别用钻头1和钻头2表示）为：dheabgcfc其中各刀具所对应的钻头如下所示：121221212各刀具对于孔型如下表所示：表16 模型3下刀具与孔型对应关系dDG h HF e DI a AC b Bg GF c E f GEJ c CIJ图5 双钻头最优化模型处理（初始状态）通过初始位置（图6），接下来刀具1在线路板上进行钻孔，刀具2在线路板外进行转换刀具，然后等刀具2转换完成，得到此时刀具路径如图6所示：图6双钻头最优化模型处理（中间状态）利用相同的思路，我们对每一个刀具进行如上分析，最后得到各刀具在线路板上行进数据如下：表17 模型3下刀具与孔型对应分析钻头121 刀具转换 行进时间 dg hf di 7.8 3.7 7.7 起点坐标 终点坐标 （88800,919800） （-311300,-52400） (202500,724400) （233100