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