1、打孔機(jī)生產(chǎn)效能的提高摘 要打孔機(jī)在加工作業(yè)時(shí)，單個(gè)鉆孔的作業(yè)時(shí)間，鉆頭的行進(jìn)時(shí)間以及刀具的轉(zhuǎn)換時(shí)間是影響生產(chǎn)效益的三個(gè)因素，每當(dāng)在鉆頭完成一個(gè)電路板的過(guò)孔加工時(shí)，鉆頭行進(jìn)的時(shí)間以及刀具轉(zhuǎn)換的時(shí)間越短，生產(chǎn)效益越高，且鉆頭行進(jìn)的總時(shí)間由鉆頭行進(jìn)路線決定，而刀具轉(zhuǎn)換總時(shí)間由線路板上各孔的位置以及鉆頭行進(jìn)方案決定。由于對(duì)同一孔型鉆孔作業(yè)的時(shí)間是相同的，所以打孔機(jī)的生產(chǎn)效能定義分析得知打孔機(jī)的生產(chǎn)效能取決與兩個(gè)因素：刀具總轉(zhuǎn)換時(shí)間T1和打孔機(jī)鉆頭的行進(jìn)時(shí)間T2。對(duì)此，分析數(shù)據(jù)得刀具轉(zhuǎn)換時(shí)間和時(shí)間的成本都遠(yuǎn)遠(yuǎn)大于打孔機(jī)行進(jìn)的時(shí)間和成本。為達(dá)到最優(yōu)的作業(yè)成本應(yīng)該是主要使刀具轉(zhuǎn)換的費(fèi)用最小，即刀具轉(zhuǎn)換的次數(shù)

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

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

4、刀具a轉(zhuǎn)換到刀具h(yuǎn)。將任一刀具轉(zhuǎn)換至其它刀具處，所需時(shí)間是相應(yīng)轉(zhuǎn)換時(shí)間的累加，例如，從刀具a轉(zhuǎn)換到刀具c，所需的時(shí)間是36s（采用順時(shí)針?lè)绞剑榱撕?jiǎn)化問(wèn)題，假定鉆頭的行進(jìn)速度是相同的，為180 mm/s，行進(jìn)成本為0.06元/mm，刀具轉(zhuǎn)換的時(shí)間成本為7元/min。刀具在行進(jìn)過(guò)程中可以同時(shí)進(jìn)行刀具轉(zhuǎn)換，但相應(yīng)費(fèi)用不減。不同的刀具加工不同的孔型，有的孔型只需一種刀具來(lái)完成，如孔型A只用到刀具a。有的孔型需要多種刀具及規(guī)定的加工次序來(lái)完成，如孔型C需要刀具a和刀具c，且加工次序?yàn)閍，c。表1列出了10種孔型所需加工刀具及加工次序（標(biāo)*者表示該孔型對(duì)刀具加工次序沒(méi)有限制）。表1：10種孔型所需加工

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

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

7、上的打孔次數(shù)進(jìn)一步擴(kuò)大。面對(duì)如此龐大的數(shù)據(jù)，若將此問(wèn)題當(dāng)做多目標(biāo)TSP來(lái)對(duì)待，模型與求解規(guī)模必定十分龐大，必須借助一些非常規(guī)方法，其結(jié)果最優(yōu)性也難以得到保證，因此我們需要對(duì)問(wèn)題進(jìn)行簡(jiǎn)化與分解。從題目描述我們得知相鄰刀具轉(zhuǎn)換一次所需時(shí)間是18s，刀具轉(zhuǎn)換成本為7元/min，而刀具行進(jìn)成本為0.06元/min，并且分析孔點(diǎn)分布數(shù)據(jù)我們可以明顯看到同一孔型的孔點(diǎn)分布相對(duì)集中，即使用某種刀具進(jìn)行多個(gè)孔點(diǎn)的連續(xù)打孔時(shí)，刀具的移動(dòng)范圍相對(duì)于全板較小，因此刀具轉(zhuǎn)換的成本遠(yuǎn)遠(yuǎn)大于刀具行進(jìn)的成本。所以想要打孔成本最小，必須要使刀具轉(zhuǎn)換次數(shù)盡可能少，于是我們將整個(gè)問(wèn)題進(jìn)行了一次簡(jiǎn)化，即認(rèn)為刀具轉(zhuǎn)換次數(shù)越少，生產(chǎn)效

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

9、小為目標(biāo)的TSP問(wèn)題。我們使用ki表示編號(hào)為i的刀具，i屬于118，所以從刀具ki轉(zhuǎn)換到刀具kj的成本為Zkij=ave * dis(i,j)其中ave表示刀具轉(zhuǎn)換一次的成本，dis(i,j)表示從刀具ki轉(zhuǎn)換到刀具kj的轉(zhuǎn)換次數(shù)。從刀具ki轉(zhuǎn)換到刀具kj的時(shí)間為Tkij=atim * dis(i,j) 其中atim表示刀具轉(zhuǎn)換一次的時(shí)間。我們令刀具轉(zhuǎn)換次序?yàn)檠h(huán)向量TURN =（Kturn1Kturn18）,有此我們可以計(jì)算刀具轉(zhuǎn)換的有向圖的可達(dá)矩陣E,其中eij=1or 0.若從ki轉(zhuǎn)換到kj的轉(zhuǎn)換行為正好存在于TURN中,則eij=1,否則為0。所以刀具轉(zhuǎn)換總成本Zt= i,j=118Z

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

11、的打孔行進(jìn)路徑。根據(jù)得到的最優(yōu)刀具轉(zhuǎn)換次序，我們可以獲得每次刀具轉(zhuǎn)換后需要加工的點(diǎn)的集合。次序刀具編號(hào)孔型1dd1,d2D,G2cc2E3bb1B4aa1,a2A,C5hh1,h2F,H6gg1,g2F,G7ff1,f2E,G,J8ee1,e2D,I9cc1,c3,c4C,I,J令次序?yàn)閜的刀具需要加工的點(diǎn)總數(shù)為Np,點(diǎn)表示為hole_p，對(duì)所有加工次序?yàn)閜的點(diǎn)進(jìn)行編號(hào)得編號(hào)為i的點(diǎn)表示為hole_p(i)因?yàn)樵趩?wèn)題1中已經(jīng)根據(jù)刀具類型對(duì)孔型進(jìn)行了分類，所以在問(wèn)題2中無(wú)須再考慮刀具類型。所以編號(hào)為i的點(diǎn)具體表示為hole_p(i) <Xp(i),Yp(i) >，其中Xp(i),Yp

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

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

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