1、C題線路板的打孔機工作流程設計摘要本文討論了電路板的打孔機工作流程中的費用及時間問題，在已知孔型、刀具及行走費用和轉刀費用的前提下，綜合考慮成本和時間，設計行走路線及換刀方案，使生產效率最高。本文中首先采用了0-1整數規劃方法（模型一），再采用二次逐邊修正法（模型二），之后采用了貪心算法（模型三）。在求解過程中，我們先考慮只打孔的情況，即遇到孔便打完，同時以最少費用為目標，對這三個模型進行比較，結果如下：模型一：該模型的變量較多，且使用0-1規劃法，對matlab以及lingo的要求較高，鑒于我們的計算機條件，該模型只有理論上的意義。模型二：在以最少費用為目標的條件下，費用為79232元，時間

2、為49188秒（約合13.66小時）。模型三：在以最少費用為目標的條件下，費用為44708元，時間為48665秒（約合13.5小時）。在以最少時間為目標的條件下，費用為374090元，時間為56298秒（約合15.6小時）。 在模型的優化部分，本文將需要兩種刀具（或三種）的孔視為兩種孔型（或三種），如C型孔，視為C1和C2兩種孔型，分別用a刀和c刀（有下刀順序），D型孔視為兩個獨立的孔D1和D2（無下刀順序）。同時綜合考慮費用和時間，建立適合大規模生產的模型，取合適的權值（以費用60%、時間40%為例），費用為49276元，時間為21272秒（約合5.9小時）。 一、問題的重述過孔是印刷線路板

3、（也稱為印刷電路板）的重要組成部分之一，過孔的加工費用通常占制板費用的30%到40%，打孔機主要用于在制造印刷線路板流程中的打孔作業。本問題旨在提高某類打孔機的生產效能。打孔機的生產效能主要取決于以下幾方面：（1）單個過孔的鉆孔作業時間，這是由生產工藝決定，為了簡化問題，這里假定對于同一孔型鉆孔作業時間都是相同的；（2）打孔機在加工作業時，鉆頭的行進時間；（3）針對不同孔型加工作業時，刀具的轉換時間。目前，實際采用的打孔機普遍是單鉆頭作業，即一個鉆頭進行打孔。現有某種鉆頭，上面裝有8種刀具a，b，c， , h，依次排列呈圓環狀，如圖1所示。bcdefgha圖1：某種鉆頭上8種刀具的分布情況而且

4、8種刀具的順序固定，不能調換。在加工作業時，一種刀具使用完畢后，可以轉換使用另一種刀具。相鄰兩刀具的轉換時間是18 s，例如，由刀具a轉換到刀具b所用的時間是18s，其他情況以此類推。作業時，可以采用順時針旋轉的方式轉換刀具，例如，從刀具a轉換到刀具b；也可以采用逆時針的方式轉換刀具，例如，從刀具a轉換到刀具h。將任一刀具轉換至其它刀具處，所需時間是相應轉換時間的累加，例如，從刀具a轉換到刀具c，所需的時間是36s（采用順時針方式）。為了簡化問題，假定鉆頭的行進速度是相同的，為180 mm/s，行進成本為0.06元/mm，刀具轉換的時間成本為7元/min。刀具在行進過程中可以同時進行刀具轉換，

5、但相應費用不減。不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，如孔型A只用到刀具a。有的孔型需要多種刀具及規定的加工次序來完成，如孔型C需要刀具a和刀具c，且加工次序為a，c。表1列出了10種孔型所需加工刀具及加工次序（標*者表示該孔型對刀具加工次序沒有限制）。表1：10種孔型所需加工刀具及加工次序孔型 A B C D E F G H I J所需刀具 a b a, cd, e* c, fg, h*d,g,f h e, c f, c一塊線路板上的過孔全部加工完成后，再制作另一線路板。但在同一線路板上的過孔不要求加工完畢一個孔，再加工另一個孔，即對于須用兩種或兩種以上刀具加工的過孔，只要保

6、證所需刀具加工次序正確即可。請建立相應的數學模型，并完成以下問題：（1）附件1提供了某塊印刷線路板過孔中心坐標的數據，單位是密爾（mil）（也稱為毫英寸，1 inch=1000 mil），請給出單鉆頭作業的最優作業線路（包括刀具轉換方案）、行進時間和作業成本。二、問題的分析本題的主要問題，是考慮行走的費用、時間以及轉刀的費用、時間，找到一條遍歷所有點的合適的行走路徑，使生產的效率達到最高。在MATLAB軟件中，我們畫出了這十種孔型的坐標（見附錄1），發現孔的數目很多，既有集中的孔，也有相對分散的孔。因此，所建的模型，應該要將所有的點都走遍，這一點可以參照TSP的相關算法，同時考慮到各種換刀問題

7、。從收集的資料可以看出，解決TSP問題的一般算法有遺傳算法，模擬退火算法，貪心算法，二次逐邊修正法等等。考慮到本題并不是完全意義上的TSP問題，本文對使用的方法進行了一定程度改進，例如考慮將路程和轉刀的因素統一成時間或是費用，使其更適合本題的要求。考慮到本題要求得出打孔的費用和時間，因此有不同生產效率的生產線，對費用和時間有不同的要求，因此在模型求解的過程中應該要考慮到對費用和時間賦予不同的權數，得出不同的行走方案，最終確定符合要求且效率高的行走路徑和轉刀方案。三、模型假設1、加工每塊板工作過程中，無刀具磨損、損壞情況，中途無間斷。2、鉆頭鉆孔、刀具加工的結果均合格，不存在殘品孔。3、鉆頭鉆孔

8、時間及費用固定，不予考慮。4、刀具行進速度保持恒定。5、周圍環境對鉆頭和刀具沒有干擾。6、鉆頭和刀具可以按照設定的路程準確行走和換刀。7、刀具行進過程中兩點之間所走路徑為直線。四、符號說明m：點的數目（2124個）。M: 將孔拆分后點的數目（2814個）。Wij :為0-1變量，Wij=1表示，i點可到達j點，Wij=0表示，i點不能到達j點。Lij :移動的費用加換刀具的費用。Ni :為0-1變量，保證有m-1條折線。mm：轉刀費用矩陣（10*10）。mm1：轉刀費用矩陣（18*18）。x ：點的橫坐標。y ：點的縱坐標。S1 ：i點到j點的費用（包括路程費和轉刀費）。S2 ：i+1點到j+

9、1點的費用（包括路程費和轉刀費）。S3 ：i點到i+1點的費用（包括路程費和轉刀費）。S4 ：j點到j+1點的費用（包括路程費和轉刀費）。S(i): i點到i+1點的費用（包括路程費和轉刀費）。F(i): i到i+1點所用時間（路程所用時間和轉刀所用時間中較大的一個）。fare：總費用。 V1：fare權數。time：總時間。V2：time權數。五、模型的建立和求解 （1），模型一的建立（0-1規劃模型）通過以上分析，我們建立了模型一，綜合考慮總路程與總費用，通過0-1規劃思想來求取最優解。 其中 表示最小費用的目標函數。 表示回路只能到達各頂點一次。 表示回路只能從各頂點出發一次。 表示兩點

10、之間只有一條路徑連接。模型一從0-1 整數規劃角度給出了一個只考慮總回路路程最短的M-TSP問題模型。對于這樣一個規劃問題，每個分組對應著一個TSP問題，相關資料顯示，由于數據量特別大現有的Lingo 和Matlab軟件不能求解或不能精確求解，故該模型只有理論意義，不能在現有的軟件下實現。下面討論用一些簡化的方法來求得問題的近似解。（2） 模型二的建立（二邊逐次修正法）1、 按照附件中給定點的順序在坐標紙上將各點依次連接，命名為路徑a1。2、 對所有的i、j，1<i+1<j<m,若S1+S2<S3+S4,則在a1中刪去路徑i到i+1和j到j+1兩條路徑，而選擇i到j和i

11、+1到j+1兩條路徑，形成新的路徑a2。3、 重復步驟（2），直到滿足條件，最后的路徑即為所求的路徑a。4、 計算總的費用： 其中mm矩陣如下（不考慮換刀時的轉刀費（從豎列到橫行）：DàC，表示D打完到C打完，需要換刀六次。ABCDEFGHIJA0124537166B1033446257C2142355346D4362535324E3453626233F1235628055G3453626233H1235628055I2142355346J2142355346取得路徑a之后即可求解出最小費用。結果表明：以最小費用為目標，需要79232元，時間為 49188秒（約合13.66小時），具

12、體的行走路徑、路徑圖及程序見附件1(按點給出初始順序依次排序為1號到2124號，打孔的順序即按編號排列，附件2、3同樣)。（3） 模型三的建立（貪心算法）1、 選擇一個起點，計算這個起點到其它各點的費用（路程費加轉刀費），選擇費用最小的一個點作為下一個起點，計算費用S(1)。2、 計算新的起點到其它點的費用（不包括已選定的點），選擇費用最小的點作為下一個起點,計算費用S(2)。3、 重復步驟2，直到遍歷各點,求出相應費用S(i)。4、 計算總的費用： 結果表明：在以最少費用為目標的條件下，費用為44708元，時間為48665秒（約合13.5小時）。同模型二相比，該模型所需的費用更少。具體的行走

13、路徑、路徑圖及程序見附件2。考慮到本設計方案要應用于大規模工業生產，故而對單個板加工時間有一定要求。基于這種考慮，本文對費用和時間進行加權。在以最少時間為目標的條件下，費用為374090元，時間為56298秒（約合15.6小時）。具體的行走路徑、路徑圖及程序見附件3。六、模型的優化由原題可知，當需要兩種（或三種）刀具的孔型，過孔不要求加工完畢一個孔，再加工另一個孔，即對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。故而將兩種刀具（或三種）的孔視為兩種孔型（或三種），則可得到18*18種換刀的情況，即mm1矩陣：ABD1D2F1F2HC1E1I1J1C2E2I2J2G1G

14、2G3A013421102432322323B102332211341411234D1320134431121211032D2431023342012122121F1233201124214144301F2124310013323233412H124310013323233412C1013421102432322323E1211243320230300143I1431023342012122121J1342112233103033210C2211243320230300143E2342112233103033210I2211243320230300143J2211243320230300143

15、G1320134431121211032G2233201124214144301G3342112233103033210針對這種方法，結合貪心算法，給出優化模型，如下：1、選擇一個起點，計算這個起點到其它各點的費用（路程費加轉刀費），選擇費用最小的一個點作為下一個起點，計算費用S(1)。2、計算新的起點到其它點的費用（不包括已選定的點和某些有下刀順序限制的點），選擇費用最小的點作為下一個起點,計算費用S(2)。3、重復步驟2，直到遍歷各點,求出相應費用S(i)。4、計算總的費用： V1、V2求一些值時的結果如下：V110.90.80.70.60.50.40.30.20.10V200.10.20

16、.30.40.50.60.70.80.91fare/元44302 44601 44566 45828 49276 52133 56024 60499 64499 73268 85252 time/秒46580 40899 34810 31972 21272 17579 14720 12196 10559 9248 8389 由上表可以看出，優化后最小費用為4.4萬元較優化前的4.5萬元降低了。最重要的是優化后的最短時間8389s（約為2.3h），較優化前的最短時間3.8萬秒大大降低了，并且當v1、v2變化時fare與time也在變化（具體關系圖見附錄2），因此，廠家需要根據利潤及銷量情況，選擇v1、v2的值，以獲得最大利潤。本文給出v1=60%、v2=40%時的具體的行走路徑、路徑圖及程序見附件4（按點給出初始順序依次排序為1號到2814號，分別為A,B,D1,D2,F1,F2,H,C1,E1,I1,J1,C2，E2,I2,J2,G1,G2,G3，附件4打孔的順序的順序即按此排列）。七、模型的評價 本文主體模型優點：省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它采用自頂向下，以迭代的方法做出相繼的選擇，每一步上都要保證能獲得局部最優解 ，使最終結果趨近于最優解。另外，根據不同權值給出不同方案，適于生產商在銷售利潤、銷售價格發生變化時，及時做出方