【正文】 電路板的打孔機(jī)工作流程設(shè)計(jì)摘要打孔機(jī)完成的打孔作業(yè)在印刷電路板的生產(chǎn)過程中占有極其重要的地位，通過合理優(yōu)化打孔路線，進(jìn)而減少生產(chǎn)時間及生產(chǎn)成本，提高生產(chǎn)效能，是生產(chǎn)作業(yè)過程中必須解決的問題。論文以總工作時間最短為目標(biāo)函數(shù)，建立數(shù)序模型，尋找最優(yōu)路徑，最短工作時間以及最少生產(chǎn)成本。忽略打孔時間，認(rèn)為總的工作時間為鉆孔行進(jìn)時間和刀具轉(zhuǎn)換時間的疊加。總的作業(yè)成本為行進(jìn)成本和刀具轉(zhuǎn)換成本之和。為了解決問題，建立了以下三種模型：模型一：機(jī)械模型，按照所需刀具種類和打孔次序，將孔進(jìn)行分類，并合理安排打孔刀具的順序，進(jìn)行分塊局部優(yōu)化。認(rèn)為用一種刀具打完相應(yīng)所有孔后，再換刀；通過蟻群算法解得最短路徑62480000mil,最短工作時間：，(元)。 模型二：簡化模型，以所有點(diǎn)為研究對象，進(jìn)行全局優(yōu)化。假定鉆孔行進(jìn)過程中不進(jìn)行換刀操作，打完某一孔后，先換刀，再行進(jìn)。利用貪婪算法和蟻群算法的混合算法解得，最短路徑為54941000mil，最短工作時間：，加工過程總費(fèi)用84570(元)。模型三：改進(jìn)模型，認(rèn)為鉆孔行進(jìn)過程中進(jìn)行換刀操作，通過引入有效換刀時間，將總的工作時間分為鉆頭行進(jìn)時間和有效換刀時間。利用貪婪算法和蟻群算法的混合算法解得，最短路徑為55231000mil，最短工作時間：，加工過程總費(fèi)用84570(元) ，經(jīng)分析該模型精確度更高，具體的刀具轉(zhuǎn)換方案及最優(yōu)路徑見附錄（一）。在模型二和模型三建立的過程中，將衡量孔的坐標(biāo)由原始的二維空間坐標(biāo)，擴(kuò)充為四維坐標(biāo)：二維空間坐標(biāo)，所需刀具種類坐標(biāo)，加工次序坐標(biāo)。這樣將一個需要多種刀具才能打完的孔型，擴(kuò)充為多個只需一種刀具的孔，有效的解決了不必一次性打完一個孔型的問題。 關(guān)鍵詞： 蟻群算法 貪婪算法 坐標(biāo)維度擴(kuò)充 群孔加工路線設(shè)計(jì)Ⅰ問題的提出與重述 印刷電路板（PCB）制造技術(shù)是電子信息制造業(yè)的重要基礎(chǔ)和組成部分，而由打孔機(jī)完成的過孔作業(yè)在其生產(chǎn)中占有重要的地位。其中加工路徑的選擇，很大程度上決定著加工效率和生產(chǎn)成本。問題旨在通過研究單鉆頭的最優(yōu)作業(yè)路線以及具體的刀具轉(zhuǎn)換方案，盡最大可能的縮短工作時間，減少作業(yè)成本，提高打孔機(jī)的生產(chǎn)效能。 Ⅱ模型假設(shè)同一孔型鉆孔作業(yè)時間相同，且由生產(chǎn)工藝決定，與問題的優(yōu)化無關(guān)，此 時間給予忽略。鉆頭行進(jìn)速度相同為,行進(jìn)成本為。相鄰兩刀具的轉(zhuǎn)換時間為,轉(zhuǎn)換的時間成本為。刀具轉(zhuǎn)換可以采用順時針和逆時針的方式，且轉(zhuǎn)換時間具有累加性。刀具在行進(jìn)過程中可以同時進(jìn)行刀具轉(zhuǎn)換，但相應(yīng)費(fèi)用不減。不同孔型所需刀具種類、個數(shù)及加工次序不同。同一線路板上的過孔不要求加工完畢一個孔，再加工另一個孔，即對于須 用兩種或兩種以上刀具加工的過孔，只要保證所需刀具加工次序正確即可。Ⅲ符號說明符號符號所表示的意義n , N原始孔數(shù)和擴(kuò)充之后的孔數(shù)擴(kuò)充后的孔的坐標(biāo)描述 為二維空間坐標(biāo)； 為刀具種類 為第i次進(jìn)行加工第i個孔和第i+1個孔的距離加工過程中刀具所走總路程刀具的行進(jìn)速度打完第i個孔，準(zhǔn)備打第i+1個孔時，刀具行進(jìn)時間。打完第i個孔，準(zhǔn)備打第i+1個孔時，刀具轉(zhuǎn)換所需時間。加工過程中刀具轉(zhuǎn)換的總時間加工過程總時間刀具行進(jìn)成本刀具轉(zhuǎn)換的時間成本加工過程總費(fèi)用打完第i個孔，準(zhǔn)備打第i+1個孔的有效刀具轉(zhuǎn)換時間。加工過程中總的有效刀具轉(zhuǎn)換時間 Ⅳ基本思想和模型的準(zhǔn)備：為了提高生產(chǎn)效能，題目已知條件指出，關(guān)鍵是減少刀具行進(jìn)時間（即縮短刀具移動路徑）和換刀時間。并且通過所給數(shù)據(jù)進(jìn)行分析，刀具行進(jìn)成本和換刀成本都與時間成正相關(guān)。因此論文以總的工作時間最短為目標(biāo)函數(shù)，建立數(shù)學(xué)模型求解，得到最優(yōu)行進(jìn)路線，最短時間以及最低成本。：充分考慮題目條件，10種孔型所需刀具種類、個數(shù)、加工次序各不相同。將原始的2124個孔進(jìn)行擴(kuò)充，原則如下：將原來衡量孔的坐標(biāo)由原始的二維空間坐標(biāo)，擴(kuò)充為四維坐標(biāo)，即：二維空間坐標(biāo)，所需刀具種類坐標(biāo)，加工次序坐標(biāo)。這樣以來原來一個的孔被分解為幾個空間位置相同,但加工刀具和加工次序不同的孔。從而有效的解決了不必一次性打完一個孔型的問題。：為實(shí)現(xiàn)高質(zhì)量、高效率、低成本的產(chǎn)品制造，優(yōu)化加工路徑是加工過程中的一個關(guān)鍵環(huán)節(jié)。但對于成千上萬的群孔，找到一條理想的加工路徑并不容易。假設(shè)在一塊已確定初始位置的印刷電路板（PCB）上加工某類孔（數(shù)量為）加工完畢后返回，則其可選路徑為條，當(dāng)時，其可選路徑為181 440條；當(dāng)時，可選路徑為條；當(dāng)時，其路徑條數(shù)已經(jīng)成為了天文數(shù)字，可以說當(dāng)加工孔的數(shù)量很大時，在所有路徑中找到一條最短路徑是不現(xiàn)實(shí)的，只能從比較理想的路徑中挑選一種作為加工路徑。為了得到理想的加工路徑，主要有以下算法：（1）、傳統(tǒng)算法：局部搜索法、貪婪算法、動態(tài)規(guī)劃法；（2）、智能優(yōu)化算法：模擬退火法、遺傳算法、蟻群算法、人工免疫算法等?？紤]到傳統(tǒng)算法和智能優(yōu)化算法的優(yōu)缺點(diǎn)，為了在有限的時間內(nèi)得到較為理想的路徑，論文選用貪婪算法和蟻群算法相結(jié)合進(jìn)行模型的求解。：在實(shí)際生產(chǎn)過程中，一塊線路板上的過孔全部加工完成后，再制作另一線路板。因此最優(yōu)路徑確定為閉合路徑，即加工起始點(diǎn)和加工結(jié)束點(diǎn)重合。為下次加工做準(zhǔn)備。（1）、首先要做的工作是繪制10種孔型在印刷電路板（PCB）上的位置。（2）、將原始的2124個數(shù)據(jù)孔進(jìn)行擴(kuò)充，得到2814個新的數(shù)據(jù)孔。Ⅴ 機(jī)械模型的建立與求解根據(jù)8種刀具將孔型進(jìn)行分類如下： 其中：a、bg、h表示刀具類型；大寫字母表示孔型，下標(biāo)表示第次打該孔型；eg: 表示第3次打孔型；現(xiàn)根據(jù)所需刀具種類，結(jié)合打孔次序，安排工作方式，使用一種刀具打完所有所需的孔型之后，再換刀進(jìn)行打孔。由于刀具行進(jìn)總路程很長，在相鄰兩次換刀時行進(jìn)路程可以忽略。由圖表知孔型第一次需用刀具，第二次需用刀具；而孔型第一次需用刀具，第二次需用刀具。由于刀具和刀具的矛盾限制，現(xiàn)將（即第2次打孔型）單獨(dú)拿出來進(jìn)行打孔，從而可以先用刀具打完孔型，在用刀具打完所需孔型。具體的打孔次序安排如下： 通過MATLAB編寫程序，利用蟻群算法進(jìn)行求解可得：（1）、各個刀具分別打孔的最優(yōu)作業(yè)路線 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔 刀具打孔（2）、最短路徑，最短時間，最低成本 最短路徑： 刀具轉(zhuǎn)換時間： 總的最短工作時間： 刀具行進(jìn)成本 刀具轉(zhuǎn)換的時間成本 加工過程總費(fèi)用 Ⅵ 簡化模型的建立與求解對于區(qū)域G中的n個原始孔進(jìn)行擴(kuò)充，得到N個新孔。設(shè)N個孔的一個排序?yàn)?其中孔有四個坐標(biāo)。具體含義如下： 孔的二維空間坐標(biāo)； 若孔和孔滿足，且，表示將原來的一個孔擴(kuò)充為兩個新孔，雖然兩個新孔的空間坐標(biāo)一致，但含義不同：（1）、表示使用第種刀具必須在第次加工時在位置上打的孔。（2）、表示使用第種刀具必須在第次加工時在相同位置上打的孔。（3）、若孔型對加工刀具，的次序沒有限制，可認(rèn)為所需刀具均可進(jìn)行第一次加工，即，=1。（4）、對于空間位置相同的兩個孔，若,則必須先打孔，后打孔；若，則孔和先后次序無關(guān)。：設(shè)為第i個孔和第i+1個孔的距離，為加工過程中刀具所走總路程，則有： 設(shè)為打完第i個孔，準(zhǔn)備打第i+1個孔時，刀具轉(zhuǎn)換所需時間，為加工過程中刀具轉(zhuǎn)換的總時間。則有：設(shè)刀具的行進(jìn)速度為,加工過程總時間為，刀具行進(jìn)成本為，刀具轉(zhuǎn)換的時間成本，加工過程總費(fèi)用。 現(xiàn)假設(shè)行進(jìn)過程中不進(jìn)行刀具轉(zhuǎn)換，則有：目標(biāo)函數(shù)：加工過程總費(fèi)用；考慮到經(jīng)過擴(kuò)展后的數(shù)據(jù)量十分龐大，因此采用貪婪算法和蟻群算法相結(jié)合的混合算法進(jìn)行編程，用貪婪算法得到一組較優(yōu)解，再通過蟻群算法進(jìn)行迭代，從而進(jìn)一步減小誤差：（1）、最優(yōu)作業(yè)路線：（2）、最短路徑，最短時間，最低成本 最短路徑： 刀具轉(zhuǎn)換時間： 總的最短工作時間： 刀具行進(jìn)成本 刀具轉(zhuǎn)換的時間成本 加工過程總費(fèi)用 Ⅶ 模型的改進(jìn)結(jié)合實(shí)際情況，考慮刀具在行進(jìn)過程中可以同時進(jìn)行刀具轉(zhuǎn)換。設(shè)在打完第i個孔，準(zhǔn)備打第i+1個孔過程中，刀具行進(jìn)時間為，刀具轉(zhuǎn)換時間，則：定義為打完第i個孔，準(zhǔn)備打第i+1個孔的過程中的有效刀具轉(zhuǎn)換時間,為加工過程中總的有效刀具轉(zhuǎn)換時間，則：若 則 ；若 則 則目標(biāo)函數(shù)變?yōu)椋? 但由于相應(yīng)費(fèi)用不減，因此加工過程總費(fèi)用為：方法同上，利用貪婪算法和蟻群算法相結(jié)合的混合算法進(jìn)行編程。（1）、最優(yōu)作業(yè)路線：（2）、最短路徑，最短時間，最低成本 最短路徑： 刀具轉(zhuǎn)換時間： 總的最短工作時間： 刀具行進(jìn)成本 刀具轉(zhuǎn)換的時間成本 加工過程總費(fèi)用 （3）、刀具轉(zhuǎn)換方案 請參照附錄（一） Ⅷ結(jié)果分析在模型一機(jī)械模型中，模型最為簡單，忽略的因素最多，因而路程最長，成本最大。對于模型二簡化模型及模型三改進(jìn)模型，由于運(yùn)用全局優(yōu)化，使得最終的路徑長度大大減少，成本也大大減少。但由于模型二假設(shè)行進(jìn)時不轉(zhuǎn)刀，且轉(zhuǎn)到次數(shù)較多，因而總時間較大。綜合考慮還是模型三改進(jìn)模型的結(jié)果更好?？傊?，由于算法精度的原因以及時間的限制，論文所得結(jié)果不一定為最優(yōu)解，但卻比較好的說明了實(shí)際情況。 Ⅸ模型的評價及應(yīng)用（1）、優(yōu)化路徑為閉合路徑，使得線路板打孔結(jié)束后又回到起點(diǎn)，為下次打孔做準(zhǔn)備，避免了每次生產(chǎn)過程中調(diào)整起始點(diǎn)，符合現(xiàn)實(shí)生產(chǎn)要求。（2）、將一個需要多種刀具才能打完的孔型，通過增加坐標(biāo)維數(shù)，擴(kuò)充為多個只需一種刀具的孔，有效的解決了不必一次性打完一個孔型的問題。（3）、通過建立以總時間最短為目標(biāo)函數(shù)，引入有效刀具轉(zhuǎn)換時間，使得研究刀具邊行進(jìn)邊換刀問題得以簡化。同時，由于在這種情況相應(yīng)費(fèi)用不減，因而這種模型所得結(jié)果更有利于提高生產(chǎn)效能。（4）、采用貪婪算法找出若干較優(yōu)路徑，然后利用蟻群算法進(jìn)行迭代，這樣一方面提高了計(jì)算精度，另一方面減少了時間復(fù)雜度。由于加工孔數(shù)眾多，在所有路徑中找到一條最優(yōu)路徑是不現(xiàn)實(shí)的，只能從比較理想的路徑中挑選一種作為加工路徑，受時間因素的制約，論文得到最終結(jié)果不一定是最優(yōu)解，只是較優(yōu)解。本問題基于TSP最優(yōu)路徑問題。經(jīng)過查找資料知道，運(yùn)用此類思想，可以解決現(xiàn)實(shí)生活中的很多問題，比如循環(huán)物流系統(tǒng)設(shè)計(jì)，郵箱取信問題，隨機(jī)車輛調(diào)度，路徑規(guī)劃，三方服務(wù)代理等。這類問題的研究及其解決對于提高生產(chǎn)效能，減少成本及其資源的浪費(fèi)具有積極作用。尤其是隨著世界經(jīng)濟(jì)的發(fā)展和市場競爭的加劇，小至一個企業(yè)大到一個民族，只有堅(jiān)持效率至上的原則，才能緊跟時代的步伐，引領(lǐng)時代的潮流。同時，此類問題的解決對于應(yīng)對當(dāng)今世界資源短缺的現(xiàn)狀，有一定的推動作用?？傊ㄟ^建立相關(guān)數(shù)學(xué)模型，使得這類問題得到很好的解決，對于整個國民經(jīng)濟(jì)體系的發(fā)展和提高具有不可估量的作用。Ⅹ 拓展與展望（1）、經(jīng)過查閱相關(guān)資料，了解到有一種雙鉆頭的打孔機(jī)：兩鉆頭可以同時作業(yè)且作業(yè)是獨(dú)立的，但為了避免鉆頭間的觸碰和干擾，受到兩鉆頭合作間距的限制。這是我們今后要研究和解決的問題。（2）、由于受到算法的制約，使得優(yōu)化效果不能達(dá)到十全十美，或多或少存在著一些缺陷，基于此，今后的研究方向是融合多種算法的優(yōu)點(diǎn)，使用混合算法。并且研究決定算法好壞的影響因素，如算法復(fù)雜度、存儲空間大小等，制定一些算法評價指標(biāo)及其權(quán)重，從而構(gòu)造出一套優(yōu)化算法的模糊綜合評價體系。參考文獻(xiàn)[1] 董臻圃，康志校等，數(shù)學(xué)建模方法與實(shí)踐 [M]，北京：國防工業(yè)出版社。[2] 王向東，戎海武，數(shù)學(xué)實(shí)驗(yàn)[M]，北京:高等教育出版社，2004。[3] 馬良，朱剛，寧愛兵等，蟻群優(yōu)化算法 [M]，科學(xué)出版社。[4] 全國大學(xué)生數(shù)學(xué)建模組委會，數(shù)學(xué)建模的實(shí)踐 [M]，北京：高等教育出版社。[5] 張振普，王大承，群孔加工路徑的優(yōu)化算法 [J]，五邑大學(xué)學(xué)報(bào)，22 (2):2530。[6] 趙曦，葉和平，廣義旅行商問題及其求解[J]，東莞理工學(xué)院學(xué)報(bào)，14(5):7579。[7] 張宏，李愛平，劉雪梅，面向TSP求解的混合蟻群算法 [J]，計(jì)算機(jī)工程，,35(8):3438。[8]