1、打孔機生產效能的提高摘 要打孔機在加工作業時，單個鉆孔的作業時間，鉆頭的行進時間以及刀具的轉換時間是影響生產效益的三個因素，每當在鉆頭完成一個電路板的過孔加工時，鉆頭行進的時間以及刀具轉換的時間越短，生產效益越高，且鉆頭行進的總時間由鉆頭行進路線決定，而刀具轉換總時間由線路板上各孔的位置以及鉆頭行進方案決定。由于對同一孔型鉆孔作業的時間是相同的，所以打孔機的生產效能定義分析得知打孔機的生產效能取決與兩個因素：刀具總轉換時間T1和打孔機鉆頭的行進時間T2。對此，分析數據得刀具轉換時間和時間的成本都遠遠大于打孔機行進的時間和成本。為達到最優的作業成本應該是主要使刀具轉換的費用最小，即刀具轉換的次數

2、最小。本文中我們使用遺傳算法尋找刀具轉換最優次序，在最優的刀具轉換方案的基礎上分步擇優打孔，即每次打完需要該種刀具的所有孔型，分別求出行進的最短路徑，建立每種刀具的當前最優擇路模型，從而獲得最高的打孔機生產效能，即完成題目要求。【關鍵詞】 生產效能 TSP 遺傳算法 刀具轉換1 問題的重述過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，過孔的加工費用通常占制板費用的30%到40%，打孔機主要用于在制造印刷線路板流程中的打孔作業。本問題旨在提高某類打孔機的生產效能。打孔機的生產效能主要取決于以下幾方面：（1）單個過孔的鉆孔作業時間，這是由生產工藝決定，為了簡化問題，這里假定對于同一孔型鉆

3、孔作業時間都是相同的；（2）打孔機在加工作業時，鉆頭的行進時間；（3）針對不同孔型加工作業時，刀具的轉換時間。目前，實際采用的打孔機普遍是單鉆頭作業，即一個鉆頭進行打孔。現有某種鉆頭，上面裝有8種刀具a，b，c， , h，依次排列呈圓環狀，如圖1所示。bcdefgha圖1：某種鉆頭上8種刀具的分布情況而且8種刀具的順序固定，不能調換。在加工作業時，一種刀具使用完畢后，可以轉換使用另一種刀具。相鄰兩刀具的轉換時間是18 s，例如，由刀具a轉換到刀具b所用的時間是18s，其他情況以此類推。作業時，可以采用順時針旋轉的方式轉換刀具，例如，從刀具a轉換到刀具b；也可以采用逆時針的方式轉換刀具，例如，從

4、刀具a轉換到刀具h。將任一刀具轉換至其它刀具處，所需時間是相應轉換時間的累加，例如，從刀具a轉換到刀具c，所需的時間是36s（采用順時針方式）。為了簡化問題，假定鉆頭的行進速度是相同的，為180 mm/s，行進成本為0.06元/mm，刀具轉換的時間成本為7元/min。刀具在行進過程中可以同時進行刀具轉換，但相應費用不減。不同的刀具加工不同的孔型，有的孔型只需一種刀具來完成，如孔型A只用到刀具a。有的孔型需要多種刀具及規定的加工次序來完成，如孔型C需要刀具a和刀具c，且加工次序為a，c。表1列出了10種孔型所需加工刀具及加工次序（標*者表示該孔型對刀具加工次序沒有限制）。表1：10種孔型所需加工

5、刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一塊線路板上的過孔全部加工完成后，再制作另一線路板。但在同一線路板上的過孔不要求加工完畢一個孔，再加工另一個孔，即對于須用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。2 問題的分析本題要求提出一個最優的打孔機打孔方案，該方案要求滿足打孔成本小同時作業完成時間盡可能短，問題描述中已經給出所有打孔點的坐標和孔型，在實際生產中，打孔機必然會不間斷進行工作，即完成一塊電路板的打孔作業后會回到初始位置和初始狀態以便開始下一塊電路板的打孔工作，因此初步將本題理解為一個多

6、目標TSP問題。3 模型的假設及符號說明3.1 模型的假設（1）假設題目中提供的數據真實準確，且允許存在一定的誤差；（2）假定對于同一孔型的作業時間都是相同的，并且不考慮鉆孔時間；3.2 符號說明符號具體含義及說明Tt刀具總轉換時間； Tm刀具行進總時間； ki編號為i的刀具；dis(i,j)從刀具ki轉換到kj的轉換次數；Zkij從刀具ki轉換到kj的成本；4 模型的建立與求解通過對題目描述以及所給數據進行進一步分析，我們可以知道每個孔的孔型和坐標，但是從數據量分析我們可以發現孔的數目在2000以上，而且部分孔型需要用兩到三種刀具進行加工，即這些孔型需要進行2-3次打孔，如此便使得一塊電路板

7、上的打孔次數進一步擴大。面對如此龐大的數據，若將此問題當做多目標TSP來對待，模型與求解規模必定十分龐大，必須借助一些非常規方法，其結果最優性也難以得到保證，因此我們需要對問題進行簡化與分解。從題目描述我們得知相鄰刀具轉換一次所需時間是18s，刀具轉換成本為7元/min，而刀具行進成本為0.06元/min，并且分析孔點分布數據我們可以明顯看到同一孔型的孔點分布相對集中，即使用某種刀具進行多個孔點的連續打孔時，刀具的移動范圍相對于全板較小，因此刀具轉換的成本遠遠大于刀具行進的成本。所以想要打孔成本最小，必須要使刀具轉換次數盡可能少，于是我們將整個問題進行了一次簡化，即認為刀具轉換次數越少，生產效

8、能越高，至此，我們將問題分解為了兩個子問題：1，刀具最優轉換順序2，優化每種刀具各自的行進路線，使行進路徑最短。（1）刀具轉換次序最優化該問題的目標即為找到一條最優的刀具轉換次序，使刀具轉換次數最少，從而使得成本最小，從表1可知每種孔型所需加工刀具和加工順序，為了方便問題的處理，我們將刀具分為18類（如表2），并對每一類進行編號（如表3）表2孔型ABCDEFGHIJ所需刀具a1b1a2 d1 c2 g1d2h2e2f3c1e1f1h1g2c3c4f2因此刀具轉換次序最優問題就變成了18個元素排序優化問題，根據前文分析，最后一個刀具加工完成后需回到初始刀具狀態，所以該問題是一個以刀具轉換總成本最

9、小為目標的TSP問題。我們使用ki表示編號為i的刀具，i屬于118，所以從刀具ki轉換到刀具kj的成本為Zkij=ave * dis(i,j)其中ave表示刀具轉換一次的成本，dis(i,j)表示從刀具ki轉換到刀具kj的轉換次數。從刀具ki轉換到刀具kj的時間為Tkij=atim * dis(i,j) 其中atim表示刀具轉換一次的時間。我們令刀具轉換次序為循環向量TURN =（Kturn1Kturn18）,有此我們可以計算刀具轉換的有向圖的可達矩陣E,其中eij=1or 0.若從ki轉換到kj的轉換行為正好存在于TURN中,則eij=1,否則為0。所以刀具轉換總成本Zt= i,j=118Z

10、kij*eij刀具轉換總時間的公式類似Tt= i,j=118Tkij*eij由模型可知Zt和Tt成正比關系，因此我們從中選擇一個Zt作為目標函數即可。因此問題模型變為目標：Min = Zt其中Zt= i,j=118Zkij*eij Zkij=ave * dis(i,j)eij屬于E from 循環向量TURN對此類以循環向量TURN為決策變量的優化模型，我們使用遺傳算法求解，通過調用Matlab遺傳工具包，帶入數據求解得到最優刀具轉換次序為。d ->c ->b ->a ->h ->g ->f ->e ->c至此，問題1得以解決。（2）優化每個刀具

11、的打孔行進路徑。根據得到的最優刀具轉換次序，我們可以獲得每次刀具轉換后需要加工的點的集合。次序刀具編號孔型1dd1,d2D,G2cc2E3bb1B4aa1,a2A,C5hh1,h2F,H6gg1,g2F,G7ff1,f2E,G,J8ee1,e2D,I9cc1,c3,c4C,I,J令次序為p的刀具需要加工的點總數為Np,點表示為hole_p，對所有加工次序為p的點進行編號得編號為i的點表示為hole_p(i)因為在問題1中已經根據刀具類型對孔型進行了分類，所以在問題2中無須再考慮刀具類型。所以編號為i的點具體表示為hole_p(i) <Xp(i),Yp(i) >，其中Xp(i),Yp

12、(i)分別表示該點的橫縱坐標。從hole_p(i)行進到hole_p(j)的成本為Mpij = ave_m * | <Xp(i),Yp(i)> , <Xp(j),Yp(j)> |其中ave_m表示刀具的單位進行成本，| <Xp(i),Yp(i)> , <Xp(j),Yp(j)> |表示兩點之間的距離，計算時采用歐幾里得距離。從hole_p(i)行進到hole_p(j)的時間為Tpij = (| <Xp(i),Yp(i)> , <Xp(j),Yp(j)> |)/v其中v為刀具行進速度。在刀具次序為p時，令行進路徑所對應的的有

13、向圖的可達矩陣為Ep,當hole_p(i)到hole_p(j)的路徑在我們選擇的路徑上時epij = 1 否則為0.所以次序p的移動總成本為Zm= i,j=1NpMpij *epij移動總時間為Tm= i,j=1NpTpij *epij由模型可知Zm和Tm成正比關系，因此我們從中選擇一個Zm作為目標函數即可。我們對此建立0-1模型進行求解。Min = ZmZm= i,j=1NpMpij *epijMpij = ave_m * | <Xp(i),Yp(i)> , <Xp(j),Yp(j)> |綜上所述，將問題轉換為一個混合整數線性規劃模型，可以使用Matlab軟件進行求解

14、。分別求得p=19時的最優路徑與最小成本。因此加工一塊電路板的總成本為Z= MinZt+p=19Min(Zmp)在matlab中根據建立模型求解，得到每種次序的刀具的最優行進路徑圖如下。次序d次序c次序b次序a次序h次序g次序f次序e次序c同時可以算出每種刀具轉換方案下的行進路徑長度如下刀具轉換方案dcbahgfec行進距離1525.82780.32880.13103745.6621.71570.21435.51159.4刀具轉換成本由最優刀具轉換次序計算得Zt = 18.9元p=19MinZmp= 949.4688元因此總成本 Z = 968.3688 元5 模型的評價與改進方向5.1 模型的評價5.1.1 模型的優點對打孔工作按照刀具轉換時