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