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，行进时间为20
3、86.33s，作业成本为948.58元，相比原本的方法，此种方法虽时间稍微多一些，但钻头行进路程变短了，也降低了成本。关键字：Matlab TSP 穷举法 一问题重述 打孔机主要用于制造印刷线路板流程中的打孔作业。为提高生产效能，需进行合理的作业安排，设计加工一块线路板的最优计划，需考虑以下几个方面：(1)单个过孔的钻孔作业时间，这是由生产工艺决定；(2)打孔机在加工作业时，钻头的行进时间；(3)针对不同孔型加工作业时，刀具的转换时间。在给定的某种砖头，上面装有8种刀具a,b.c ,h,依次排列呈圆环状，如图 1所示：bcdefgha 图1：某种钻头8种刀具的分布情况而且8种刀具的顺序固定，不
4、能调换。加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间为18s。作业时，可采用顺（逆）时针旋转的方式转换刀具。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加。为简化问题，假定钻头的行进速度是相同的，为180mm/s，行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。 不同刀具加工不同孔型，表一列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g
5、, fhe, cf, c 同一线路板上的过孔不要求加工完毕一个孔，再加工令一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。要求：根据提供的数据给出单钻头的最优作业线路（包括刀具转换方案）、行进时间和作业成本；(2)设计一种双钻头的打孔机，（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。(i)针对附件1的数据，给出双钻头作业时的最优作业线
6、路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？(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：方案2：方案3：方案4：方案5：方案6：方案7：方案8：方案
9、9：方案10：方案11：方案12：方案13：方案14：方案15：方案16：通过分析各方案的转换次数可以发现，最佳的刀具转换方案，也就是转换次数最小的方案，是方案8：。根据方案8，可以求得每种刀具所能打的孔型的最佳方案。针对方案8，每次转化钻头所需打的孔型见表1：表1钻头对应的钻孔孔型序列步骤刀具每一步对应刀具所能打的孔型1、2E3bB4A、C5、6F、G7fG、J、E8I、D9cC、J、I（2）线路板钻孔分布对于问题一，我们首先做出钻孔在线路板的分布情况，如图1所示图1 线路板钻孔分布图（3）最优路径模型通过穷举法，我们得到了刀具转化的最优方案。我们把孔中心看做城市，钻头看做商人，那么钻头打好
10、一种孔型就如同商人遍访每一个城市，商人行进路程S即为钻头的作业距离。若问题的解空间M可表示为的所有排列的集合，即其中，每个排列Mi表示遍访n个城市的一个路径，表示第i次访问城市j。原始数据矩阵为N为城市编号，X为城市的x轴坐标，Y为城市的y轴坐标。那么即可得到原始数据矩阵的x坐标，y轴坐标。要算出每个点和其他所有点的距离，需要将，延拓成n阶方阵，定义一个n阶方阵：应为要通过向量化的方法计算距离矩阵，所以要进行转置记为：,于是有i城市到j城市的距离矩阵：那么我们可以得到一个访问所有城市的路径总长度：通过模拟退火算法得到函数C的一个最优值。下面我们以孔型G和刀具g为例进行说明，虽然钻孔型G时，要用
11、到d、g、f三种刀具，在这里我们只选取打孔型G时，使用刀具g这一步骤。在附录中我们可以得到孔型G的中心坐标数据，将它编号如下表2：表2 孔型G的中心坐标XYXY1-301300-1920011-321300-424002-3013002340012-321300434003-301300-4240013-321300-624004-3013004340014-321300643005-301300-6240015-3213008006-3013006430016-321300843007-301300800171530008926008-30130084300181730008926009-3
12、21300-192001919300089260010-3213002340020213000892600根据模型我们得到这一个距离矩阵表3 矩阵里的数据表（105 mil）1220100.42605.246120.426005.1789.205.24615.17890在这里i=20，j=20。由于数据太多，就不在具体写出矩阵中数据时每个点和其他的所有点的距离即关系矩阵。对角线上，因为是各点到自己本身的距离，所以值为0。然后第一行表示点1到其他各点的距离，如点1到2点的距离是0.4260105 mil.第一列表示各点到点1的距离，如点20到点1的距离是5.2461105 mil.进而我们得到我
13、们的目标函数，假设为总的距离。开始按照原始数据的路径来行进,即顺序1,2,3,20。我们将这个顺序集合表示为:D=1,2,20目标函数是这个总的距离达到最小值即：下面我们通过随机选择两个点或三个点，交换他们的顺序，得到一个新解记为长度,比较S和的大小，将小的程度保留。然后继续进行随机选取点和求总长度，比较得较小者。经过多次的随机选择，得到最优的即最小的总长度并记录最优的路径。这样就得到了最短路径通过上面的模型我们得到了在打G孔型时g刀具的最优路径及最短距离。最优路径： 最短距离：2.3017e+006由图2可以看出，使用退火算法模拟最优路径，很好地求解了钻头打孔的最短路径，使得个坐标点之间距离
14、最优化，最后结果得到的路径长度比较满意。路径图2：图2 “g”钻头最优打孔路线图 通过以上对“f”钻头的分析与求解，我们采用相同的方法对九个序列分别进行求解，可得各钻头在线路板上最短路径如表4所示。表4 各钻头在线路板上路径起终点以及路径长度（mil）钻头起点坐标终点坐标长度d-27400,54100-17400,541006.2075c126200,845600106800,837200b-88200，370000-61800,390400a-54200,205000-6400，221600h-311300，-5240069000，-1800g-301300，-62400-311300,74
15、300f-321300,64300-321300,43400e-2900，54100235855,832162c-65800,473600-65400,473600通过上表的起点和终点坐标，可以求出刀具转换过程中路径长度，如表5所示表5 单钻头下刀具转换过程中的移动路径长度（mil）起点终点起点坐标终点坐标移动路径长度-17400,54100126200,845600106800,837200-88200，370000-61800,390400-54200,205000-6400，221600-311300，-52400g69000，-1800-301300，-62400gf-311300,7
16、4300-321300,64300-321300,43400-2900，54100235855,832162-65800,473600通过表2中数据我们可以得到，各钻头在线路板上最优总路径长度（单位：mil）为：（4）单钻钻头打孔费用、作业时间及作业成本 通过以上对模型的分析，可以得到最优作业线路下行进时间的关系表达式为：其中代表最优作业线路下刀具行进的总时间，代表最优作业线路下刀具从i转换到j所消耗的时间由于刀具行进总时间可由总路径长度S求得，因此，我们接下来对刀具转换时间进行考虑，刀具转换的时间为18s，大部分的刀具转换都在移动路径中转换好了，除去，它的移动路径中所需时间小于刀具转换时间，
17、那么将他记为18s。最后得出总时间=6814s2、单钻头打孔机在线路板最优费用求解通过对题目的分析，可以得出作业成本的关系式如下： 其中，代表钻头从钻头转换到钻头所需的费用（单位：元）；代表第个钻头在线路板上前进的总费用；表示钻头转换所需要的费用（单位：元）。在模型2对钻头模型分析可知， 其中，代表从钻头转换到钻头所需要的时间（单位：秒）；代表刀具转换的时间成本（单位：元）。因此，钻头转换过程中前进所需的费用（单位：元）为： 钻头转换过程中转换所需要的费用（单位：元）为： 所以，最后所需的费用（单位：元）为：=64416（元）5.2问题二的求解双钻头作业的最优生产效应分析1研究双钻头协同工作时
18、对线路板区域的分块在考虑双钻头协同工作的模型时，由于两个钻头同时工作，且相距不小于3cm，因此，我们考虑将22.8m30.48m线路板分成四块，换分区域的要求考虑如下：1、在任何情况下都要满足两钻头直接的距离小于3cm；2、考虑四个区域钻孔密集程度相当；3、考虑双钻头工作时转换区域时候时间相对较短。 因此，我们综合考虑上述情况，最终得到处理分块方式如图3所示：图3 双钻头作业时区域分块图上图三条线分别代表的直线方程是：。（2）双钻头作业时线路板各区域钻孔路径分析对于区域1，我们依然采用问题一的方法对其进行研究。其刀具的最短转换顺序仍为：,因此，我们使用模拟退火算法对区域1的孔型进行最短路径求解
19、，可得各钻孔行进时的最短路径如表6所示：表6 双钻头作业时区域1各钻头行进最短路径钻头起点坐标终点坐标路径长度d-220525,556200-301300,434001.584104c-244200,278000-271900,4265001.494106b-249800,758600-215000,-272005.090105a-244400,258600-298800,9190003.401105h-311300,-52400-319400,4565002.310105g-301300,84300-321300,-424001.862106f-268400,-65200-298800,90
20、80001.640106e-276996,259221-220525,5562002112106c-309800,908000-279400,-652001.643106由上表可得区域1的最短行进长度为2、区域1在最优化效应下最短时间求解由各钻头前进最短路径数据，可以得到区域1打孔路径示意图4图4 分块后区域1最优化路线示意图由此，我们对区域1钻头转换过程中的路径长度进行求解，可以得到数据表7所示：表7 区域1刀具转换过程中的路径长度起点终点起点坐标终点坐标路径长度dc-301300,43400-244200,2780002.41105cb-271900,426500-249800,75860
21、03.32105ba-215000,-27200-244400,2586002.87105ah-298800,919000-311300,-524009.71105hg-319400,456500-301300,843003.73105gf-321300,-42400-268400,-652005.76104fe-298800,908000-276996,2592219.71105ec-220525,556200-309800,9080003.63105由上表可以得出区域1早刀具转换中行进的距离为2.93106mil综上在区域1中作业过程中花费的是时间为：其中，代表区域1中钻头行进所消耗的时间
22、，代表区域1中钻头转换时消耗的时间。综上，可一得到区域1作业过程中花费的时间=18063、区域1在最优生产效应下费用求解由于区域1沿用问题1中的求解方法，因此把数据带入=19561（3）区域2、3和4最优化路径分析通过上述区域1的分析，我们采用相同的思路对区域2、3和4进行分析求解，最终获得处理数据和结果如下所示：表8 双钻头作业时区域2各钻头行进最短路径钻头起点坐标终点坐标路径长度d22500,662300312200,8982001.18106c30200,720200137000,8994008.08105b-600,81220092300,8163007.01105a-38800,64
23、8800447700,8969001.32106h4980,70690029780,8926004.90105g-4980,70690021300,8926006.29105f193000,892600447700,9079001.53106e-225600,662300489989,6128701.52106c27800,659800489989,6118701.76106表9 双钻头作业时区域3钻头行进最短路径钻头起点坐标终点坐标长度66118,111992-5400,4692008.28105-136600，-5280039300,4498006.6710622800,842003520
24、0,4858004.3410669000，-1800-5285,5259005.5110569000，-180069000,607006.25104f62600,15800-5400,4692001.1310653200,60800-182000,3210495.92105-182000,32104953200,608005.92105-60600,4140035200,4858001.72106表10 双钻头作业时区域4各钻头行进最短路径钻头起点坐标终点坐标长度332900,2800169000,4170009.91105143000,16600114600,454002.301052204
25、00，-30500169100,5454003.05106226953,133142203331,1252682.01106165000，-1200177500,613005.09105165000，-180081500,607002.80105f100447,511188219600,284001.52106293800，-50200169000,4170001.03106317000,217200340400，-542001.65106表11 区域2刀具转换过程中的路径长度起点终点起点坐标终点坐标路径长度312200,89820030200,7202003.68105137000,8994
26、00-600,8122001.6310592300,816300-38800,6488005.15105447700,8969004980,7069004.82105g29780,7871004980,7069008.03104gf21300,892600193000,8926001.72105f447700,907900-225600,6623007.17105489989,612870-27800,6598002.85105表12 区域3刀具转换过程中的路径长度起点终点起点坐标终点坐标路径长度-5400,469200-136600，-528005.3810539300,4498002280
27、0,842003.6610535200,48580069000，-18004.89105-5285,52590069000，-18005.33105g69000,6070062600,608004.54105gf-5400,46920053200,608004.13105f-182000,321049-182000,321049053200,60800-60600,414001.15105表13 区域4刀具转换过程中的路径长度起点终点起点坐标终点坐标路径长度16900,0,417000143000,166004.01105114600,45400220400，-305001.301051691
28、00,545400226953,1331424.1610520333,1,125268165000，-12001.32105ag177500,61300106500-18009.50105gf81500,60700100447,5111884.51105f219600,28400293800，-502001.08105169000,417000317000,2172002.491052.区域2、3和4最优化路径分析 通过表9-表14，可以得到区域2、3、4刀具转换的路径长度和行进的路径长度关系如下表：表14 各区域刀具行进和转换路径长度表汇总区域序号区域2区域3区域4刀具转换的路径长度4.43
29、1062.381061.98106行进的路径长度9.951061.691061.15106由表 可知，打孔机在区域2、3、4分别打孔所需的时间为：208928131957打孔机在区域2、3、4分别打孔所需的费用（单位：元）为：2196129508261243.双钻头下四区域转换方案分析 通过对双钻头下刀具转换时间、和的分析，综合考虑划区域的要求，最终我们选择一开始在区域1和区域4两钻头协同工作，接下来通过各区域转换钻头的起点和终点，对区域1、4转换区域的方案进行分析，得到各区域起终点关系如下：表15 区域转换方案分析区域转换方案钻头行进路径长度（单位：mil）区域1区域25.89105区域4区
30、域32.80105区域1区域38.80105区域4区域26.19105通过表 的分析，我们得出双钻头下区域选取方案为：区域1区域2和区域4区域3。接下来，我们对此方案下的生产效能进行分析。4、双钻头四区域模型下生产效能计算 通过以上的分析，可得转换后总时间为：=8865最后的费用为1169475.2.3.双钻头四区域模型的评价 首先，我们对题意进行了详细分析，得出了双钻头行进路线下对钻头进行的要求，然后，为满足双钻头直接距离不小于3cm我们采用了分区域模型，通过分别对各区域钻孔数据采用模拟退火算法，求出各个区域钻头行进的时间以及费用，最后得出钻换后的时间为T=8865费用为W=116947通过
31、与但钻头结果的对比，发现TT，WW ，得出双钻头四区域模型并不能很好地处理双钻头问题，分析原因，归结于各钻头转换所需要的时间太长（18s），而四区域模型对双钻头的转换时间要求比较高，因此，我们接下来基于双钻头四区域模型的思想对该模型进行改进，即减少钻头转换的次数，最终以获得更优化的生产效能。5.2.4.模型3：双钻头工作下最优化效能处理模型1.模型3的建立由双钻头钻孔下四区域分块模型不能很好地解决工作的最优化问题，因此，接下来我们考虑线路板整体分析，最终采用如下思路进行模型搭建：首先考虑双钻头打孔机下如何合理利用两个钻头协同使得工作效率进一步提高，我们考虑采用双钻头分别独立工作的思路，即钻头1
32、在线路板上行进的时候钻头2在转换道具，待钻头2转换道具结束开始进入线路板进行打孔，带钻头1打孔结束退出线路板处3cm，钻头2进入线路板，以此往复。最后对表1分析得到道具加工序列（假设两钻头分别用钻头1和钻头2表示）为：其中各刀具所对应的钻头如下所示：各刀具对于孔型如下表所示：表16 模型3下刀具与孔型对应关系dheabgcfcDGHFDIACBGFEGEJCIJ图5 双钻头最优化模型处理（初始状态） 通过初始位置（图6），接下来刀具1在线路板上进行钻孔，刀具2在线路板外进行转换刀具，然后等刀具2转换完成，得到此时刀具路径如图6所示：图6双钻头最优化模型处理（中间状态）利用相同的思路，我们对每一
33、个刀具进行如上分析，最后得到各刀具在线路板上行进数据如下：表17 模型3下刀具与孔型对应分析钻头刀具转换行进时间起点坐标终点坐标1dg7.8（88800,919800）2hf3.7（-311300,-52400）(202500,724400)1di7.7（233100,647300）(-301600,724400)2ac18.3（-91400,306600）(-232600,873000)2b17.24（-164700,40510）(255600,-55500)1gf3.3（-311300,-9200）(213000,892600)2e5.2（106800,837200）(233000,557
34、600)1egj9.3（-268400,-65200）(-199800,203200)2cij12.7（894747,87300）（-38800,89447）因此，我们采用模型2的思路使用模拟退火算法，求得在此模型下总费用的大小为：钻孔工作的总时间为由此可以得到在双钻头协同工作时时间花费大为减少，而所需的费用差别不大，效率提高 。通过对比上一个模型，我们可以看出，分治法的应用使两钻头协同工作时的时间花费更小，因此，我们有理由相信，双钻头工作更有利于打孔机减小生产费用，更有利于提高打孔机的效能。5.2.4.两钻头艰巨对产生效能的影响分析模型为了研究打孔机的两钻头合作间距对作业路线和生产效能产生的
35、影响，我们分别对钻头间距为2、3、4和5厘米进行总作业费用和总作业时间的求解，然后建立两钻头合作间距与作业的时间、作业时的成本的关系，如表18所示：表18 两钻头合作间距与生产效应关系表两钻头间距（cm）23456710总费用（元）100498103645107829114563118346121947125683总时间（s）81618437873292149456974112101通过以上表格分析，随着两钻头合作间距的增加，打孔机工作时的总费用和总时间都随之增加，两钻头合作间距每增加1cm，总费用约增加3000元，因此，两钻头间距对生产效应有一定影响，因此，在实际生产中，我们要更多地考虑两钻
36、头合作间距的大小，以获得最优生产效应。六、模型的优缺点七、模型的推广与评价（1）我们对题意进行了详细的分析，得出了双钻头行进路线下对钻头行进的要求。然后，为满足双钻头直接距离不小于3com，我们采用了分区域模型，通过分别对各区域钻孔数据采用模拟退火算法，求出各区域钻头行进的时间以及费用，最后得出转换后的时间为=8437，费用=103645元。通过与单钻头结果的对比，发现,，得出双钻头四区域模型并不能很好的处理双钻头问题。分析原因，归结于各钻头转换所需的时间太长（18s），而四区域模型对钻头的转换时间要求比较高，因此，我们接下来基于双钻头四区域模型的思想对模型进行改进，即减少钻头转换的次数，最终以获得更优化的生产效能。（2）模拟退火算法不仅能用在工业处理最佳效能问题上，还可以用在机器学习、信号处理等等其他领域的问题，具有很好的推广价值。（2）本模型求解思路可以推广到求解更一般的最优化问题模型。
