數(shù)學(xué)模型打孔機(jī)效率提高

1、福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院（數(shù)學(xué)類課程）課程論文報(bào)告課程名稱：數(shù)學(xué)模型課程論文題目：打孔機(jī)生產(chǎn)效能的提高姓 名：系：專 業(yè)：年 級(jí)：學(xué) 號(hào)：指導(dǎo)教師：職 稱：2013年 1月7日福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院數(shù)學(xué)類課程課程論文結(jié)果評(píng)定評(píng)定內(nèi)容評(píng)定指標(biāo)評(píng)分權(quán)值評(píng)定成績(jī)工作態(tài)度工作努力，遵守紀(jì)律；工作作風(fēng)嚴(yán)謹(jǐn)務(wù)實(shí)；按期完成規(guī)定的任務(wù)0.1論文格式格式規(guī)范、結(jié)構(gòu)合理、內(nèi)容完整0.1論文質(zhì)量假設(shè)合理；模型正確；求解準(zhǔn)確；表述清晰。立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理；實(shí)驗(yàn)正確，分析處理科學(xué)；文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊全，書(shū)寫(xiě)工整規(guī)范，圖表完備、整潔、正確；論文結(jié)果有應(yīng)用價(jià)值；0.6工作創(chuàng)新工

2、作中有創(chuàng)新意識(shí)、有見(jiàn)解；對(duì)前人工作有改進(jìn)或突破，或有獨(dú)特見(jiàn)解；0.1工作量與工作難度工作量飽滿，工作難度大0.1成績(jī)：指導(dǎo)教師簽字：任務(wù)下達(dá)日期：2012年12月12日評(píng)定日期：2013年1月15日目錄摘要1關(guān)鍵詞11 問(wèn)題重述22 問(wèn)題分析23 模型假設(shè)34 模型準(zhǔn)備（模擬退火算法簡(jiǎn)介）35 模型的建立與求解45.1 模型建立45.2 模型求解66 模型分析與評(píng)價(jià)12參考文獻(xiàn)13附錄A 單轉(zhuǎn)頭優(yōu)化路線圖（部分）14附錄B MATLAB程序代碼（部分）16打孔機(jī)生產(chǎn)效能的提高摘要過(guò)孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，過(guò)孔的加工費(fèi)用通常占制板費(fèi)用的30%到40%，打孔機(jī)主要用于

3、在制造印刷線路板流程中的打孔作業(yè)。因此打孔機(jī)效能的提高是降低制板費(fèi)用的重要途徑之一。本文旨通過(guò)建立數(shù)學(xué)模型，實(shí)現(xiàn)刀具轉(zhuǎn)換最優(yōu)順序的前提下，運(yùn)用模擬退火算法找到最優(yōu)線路，及最短距離。使作業(yè)成本和行進(jìn)時(shí)間達(dá)到最低，以此減少打孔機(jī)總打孔成本。針對(duì)單轉(zhuǎn)頭的作業(yè)方式，先根據(jù)刀具轉(zhuǎn)換的約束和孔型的約束，用窮舉法得到刀具最優(yōu)轉(zhuǎn)換順序，即d-c-b-a-h-g-f-e-d-c，再根據(jù)刀具裝換方案確定打孔方案，即將孔分成9類，即D,G、E、B、A,C、F,H、F,C、E,G,F、D,I和C,I,J，同一類孔在同一時(shí)間段內(nèi)用同一種刀具進(jìn)行打孔，沒(méi)有先后順序的約束，因此我們對(duì)每一類孔都用模擬退火算法進(jìn)行搜索最優(yōu)路線

4、，進(jìn)而得到問(wèn)題的優(yōu)化解。經(jīng)計(jì)算得到的結(jié)果是：采用單轉(zhuǎn)頭加工方式作業(yè)成本為95694元，行進(jìn)時(shí)間2小時(shí)22分鐘。針對(duì)雙轉(zhuǎn)頭的作業(yè)方式，由于兩個(gè)鉆頭獨(dú)立工作，兩個(gè)鉆頭可以同時(shí)進(jìn)行打孔，也可以一個(gè)鉆頭打孔，另一個(gè)鉆頭行進(jìn)或轉(zhuǎn)換刀具。但為了避免鉆頭間的觸碰和干擾，在過(guò)孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm。所以我們就將線路板根據(jù)孔數(shù)平均分成兩個(gè)區(qū)域（一個(gè)轉(zhuǎn)頭負(fù)責(zé)打一塊區(qū)域的孔），然后再對(duì)每一區(qū)域里的孔采用單轉(zhuǎn)頭打孔方式找出的優(yōu)化路線即可得到問(wèn)題的一個(gè)優(yōu)化解；再驗(yàn)證該解是否符合要求（即是否符合任何時(shí)刻兩鉆頭間距都不小于3cm），如果不符合，就再求解（由于模擬退火算法求出的是近似解，所以每次求出的

5、解基本都會(huì)不一樣），再驗(yàn)證，再求解，再驗(yàn)證直到找到符合的解為止。經(jīng)計(jì)算得到的結(jié)果是：采用雙轉(zhuǎn)頭加工方式作業(yè)成本為98239元，行進(jìn)時(shí)間1小時(shí)24分鐘，相對(duì)于單轉(zhuǎn)頭打孔機(jī)，效能提高40%左右。針對(duì)打孔機(jī)的兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響，本文考慮到合作間距太大會(huì)影響作業(yè)路線；合作間距太小，兩轉(zhuǎn)頭工作時(shí)可能會(huì)產(chǎn)生相互影響。因此合作間距控制不合理會(huì)浪費(fèi)資源，降低產(chǎn)品加工質(zhì)量，進(jìn)而影響到生產(chǎn)效能。所以，要提高生產(chǎn)效能就得設(shè)置一個(gè)合理的合作間距。關(guān)鍵詞：窮舉法；模擬退火算法；TSP問(wèn)題251 問(wèn)題重述過(guò)孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，其加工費(fèi)用通常占制板費(fèi)用的30%到4

6、0%，打孔機(jī)主要用于在制造印刷線路板流程中的打孔作業(yè)。由于打孔機(jī)的生產(chǎn)效能主要取決于以下幾方面：（1）單個(gè)過(guò)孔的鉆孔作業(yè)時(shí)間；（2）打孔機(jī)在加工作業(yè)時(shí)，鉆頭的行進(jìn)時(shí)間；（3）針對(duì)不同孔型加工作業(yè)時(shí)，刀具的轉(zhuǎn)換時(shí)間。而目前實(shí)際采用的打孔機(jī)普遍是單鉆頭作業(yè)。現(xiàn)有某種鉆頭，上面裝有8種刀具a，b，c， , h，依次排列呈圓環(huán)狀，而且8種刀具的順序固定，不能調(diào)換。在加工作業(yè)時(shí)，刀具可以轉(zhuǎn)換，相鄰兩刀具的轉(zhuǎn)換時(shí)間是18 s。將任一刀具轉(zhuǎn)換至其它刀具處，所需時(shí)間是相應(yīng)轉(zhuǎn)換時(shí)間的累加。為了簡(jiǎn)化問(wèn)題，假定鉆頭的行進(jìn)速度是相同的，為180 mm/s，行進(jìn)成本為0.06元/mm，刀具轉(zhuǎn)換的時(shí)間成本為7元/min。

7、刀具在行進(jìn)過(guò)程中可以同時(shí)進(jìn)行刀具轉(zhuǎn)換，但相應(yīng)費(fèi)用不減?，F(xiàn)有一種線路板，給定上面孔型所需的加工刀具和刀具加工次序。一塊線路板上的過(guò)孔全部加工完成后，再制作另一線路板。但在同一線路板上的過(guò)孔不要求加工完畢一個(gè)孔，再加工另一個(gè)孔，即對(duì)于須用兩種或兩種以上刀具加工的過(guò)孔，只要保證所需刀具加工次序正確即可。請(qǐng)建立相應(yīng)的數(shù)學(xué)模型，根據(jù)附件給的數(shù)據(jù)（單位：密爾），完成以下問(wèn)題：（1）請(qǐng)給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進(jìn)時(shí)間和作業(yè)成本。（2）為提高打孔機(jī)效能，現(xiàn)在設(shè)計(jì)一種雙鉆頭的打孔機(jī)（每個(gè)鉆頭的形狀與單鉆頭相同），兩鉆頭可以同時(shí)作業(yè)，且作業(yè)是獨(dú)立的，即可以兩個(gè)鉆頭同時(shí)進(jìn)行打孔，也可以一個(gè)

8、鉆頭打孔，另一個(gè)鉆頭行進(jìn)或轉(zhuǎn)換刀具。為避免鉆頭間的觸碰和干擾，在過(guò)孔加工的任何時(shí)刻必須保持兩鉆頭間距不小于3cm（稱為兩鉆頭合作間距）。為使問(wèn)題簡(jiǎn)化，可以將鉆頭看作質(zhì)點(diǎn)。（i）給出雙鉆頭作業(yè)時(shí)的最優(yōu)作業(yè)線路、行進(jìn)時(shí)間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機(jī)進(jìn)行比較，其生產(chǎn)效能提高多少？（ii）研究打孔機(jī)的兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。2 問(wèn)題分析 本題是一題優(yōu)化問(wèn)題，目標(biāo)是總費(fèi)用最少和總時(shí)間最少。 1、針對(duì)問(wèn)題一：考慮到：（2-1）所以想要總費(fèi)用最少，就得使刀具轉(zhuǎn)換次數(shù)最少和行進(jìn)總路程最少。約束條件是：刀具的轉(zhuǎn)換順序固定；不同的孔需要不同的刀具。因此我們先根據(jù)不同的孔需要不同的刀具，以

9、刀具轉(zhuǎn)換總次數(shù)為目標(biāo)，先得到刀具的轉(zhuǎn)換方案；再根據(jù)刀具裝換方案確定打孔方案，即將孔根據(jù)刀具轉(zhuǎn)換方案進(jìn)行分類，同一類孔在同一時(shí)間段內(nèi)用同一種刀具進(jìn)行打孔，沒(méi)有先后順序的約束，因此我們對(duì)每一類孔都用模擬退火算法進(jìn)行搜索最優(yōu)路線，進(jìn)而得到問(wèn)題的一個(gè)解。2、針對(duì)問(wèn)題二：考慮到雙轉(zhuǎn)頭，我們就將線路板根據(jù)孔橫向平均分成兩部分，即作一條豎線L1，使兩邊的孔數(shù)差值的絕對(duì)值小于或等于1，此時(shí)L1稱平分分界線。再以1.5cm為距離，在L1兩邊做平行線L2和L3，若L2、L3之間沒(méi)有孔，則稱L1為最優(yōu)分界線。若L1不是最優(yōu)分界線，則適當(dāng)移動(dòng)L1使其變成最優(yōu)分界線。若線路板不存在最優(yōu)分界線，則以平分分界線L1為界線，

10、將線路板分成兩部分，分別用兩個(gè)轉(zhuǎn)頭進(jìn)行打孔，再利用問(wèn)題一的方法求出每一部分的優(yōu)化路線即可得到問(wèn)題的一個(gè)解；再驗(yàn)證L2和L3之間的孔是否符合要求，如果不符合，就再求解（由于模擬退火算法求出的是近似解，所以每次求出的解基本都會(huì)不一樣），再驗(yàn)證，再求解，再驗(yàn)證直到找到符合的解為止。而本題給的數(shù)據(jù)經(jīng)過(guò)計(jì)算發(fā)現(xiàn)存在最優(yōu)分界線L1，所以就以L1為界線，將線路板分成兩部分，分別用兩個(gè)轉(zhuǎn)頭進(jìn)行打孔，這樣兩轉(zhuǎn)頭之間的距離在任何時(shí)刻都會(huì)大于3cm。再利用問(wèn)題一的方法求出每一部分的優(yōu)化路線即可得到問(wèn)題的解。3 模型假設(shè)1、假設(shè)單孔轉(zhuǎn)孔時(shí)間都是相同的；2、假設(shè)轉(zhuǎn)頭的行進(jìn)速度是勻速的；3、假設(shè)所有的孔都是一個(gè)點(diǎn)；4 模

11、型準(zhǔn)備（模擬退火算法簡(jiǎn)介）4.1、模擬退火算法原理：模擬退火算法得益于材料的統(tǒng)計(jì)力學(xué)的研究成果。統(tǒng)計(jì)力學(xué)表明材料中粒子的不同結(jié)構(gòu)對(duì)應(yīng)于粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運(yùn)動(dòng)和重新排列。在低溫條件下，粒子能量較低。如果從高溫開(kāi)始，非常緩慢地降溫（這個(gè)過(guò)程被稱為退火），粒子就可以在每個(gè)溫度下達(dá)到熱平衡。當(dāng)系統(tǒng)完全被冷卻時(shí)，最終形成處于低能狀態(tài)的晶體。根據(jù)Metropolis規(guī)律，如果用粒子的能量定義材料的狀態(tài)，假設(shè)材料在狀態(tài)之下的能量為，那么材料在溫度時(shí)從狀態(tài)進(jìn)入狀態(tài)就遵循如下規(guī)律：a、如果，接受該狀態(tài)被轉(zhuǎn)換。 b、如果，則狀態(tài)轉(zhuǎn)換以如下概率被接受：（4-1）其中是物理學(xué)中

12、的波爾茲曼常數(shù)，是材料溫度。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子t、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。4.2、模擬退火算法解決TSP問(wèn)題模型：TSP問(wèn)題，即旅行商問(wèn)題。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑

13、的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。模擬退火算法描述如下：a、解空間：解空間S可表示為1,2,N的所有固定的起點(diǎn)和終點(diǎn)的循環(huán)排列集合，即：（4-2）其中每一個(gè)循環(huán)排列表示一種行走方案，表示第i次到達(dá)j城市。b、目標(biāo)函數(shù)：目標(biāo)函數(shù)為經(jīng)過(guò)所有城市的總路程或稱代價(jià)函數(shù)，我們要求：（4-3）而迭代有下面3步構(gòu)成：c、新解的產(chǎn)生(2變換法)：任取序號(hào)u，v（u<v），交換u與v之間的順序，此時(shí)新路徑為：（4-4）d、代價(jià)函數(shù)差：（4-5）e、接受準(zhǔn)則：（4-6）如果，則接受新的路徑；否則，以概率接受新的路徑，即若大于0

14、到1的隨機(jī)數(shù)則接受。f、降溫：利用降溫系數(shù)進(jìn)行降溫，即：得到新的溫度，一般取。g、結(jié)束條件：用選定的終止溫度(一般取)，判斷退火過(guò)程是否結(jié)束。若，算法結(jié)束，輸出當(dāng)前狀態(tài)。5 模型的建立與求解5.1 模型建立目標(biāo)函數(shù)：（5-1）（5-2）其中：表示總成本；表示刀具轉(zhuǎn)換總成本；表示轉(zhuǎn)頭行進(jìn)總成本；n為刀具轉(zhuǎn)換總次數(shù)；S為轉(zhuǎn)頭行進(jìn)總路程；為刀具轉(zhuǎn)換單位次的成本；為轉(zhuǎn)頭行進(jìn)單位路程的成本。所以現(xiàn)在就是要計(jì)算n的最少值和S的最少值：即。對(duì)于，可以這樣考慮：從序列a,b,g,h,a,b,g,h,a,b,（刀具的轉(zhuǎn)換順序，也可以全部逆序）中取出一連續(xù)子列（刀具的一種轉(zhuǎn)換方案），再任取一種孔型，得到其所需加工

15、刀具的加工次序，則子列中至少有一對(duì)元素（子列中的兩個(gè)元素組成有序?qū)Γ┑拇涡蚺c加工次序相同（該轉(zhuǎn)換方案可行），則這個(gè)子列的元素個(gè)數(shù)減1就為n。使得n達(dá)到最小的子列以下就稱最優(yōu)子列。用MATLAB進(jìn)行窮舉得到這個(gè)最優(yōu)子列為d,c,b,a,h,g,f,e,d,c，有10個(gè)元素，所以最少轉(zhuǎn)換次數(shù)n=9。得到轉(zhuǎn)換方案及對(duì)應(yīng)打孔的孔型如圖2圖2 刀具轉(zhuǎn)換方案及對(duì)應(yīng)加工的孔型根據(jù)刀具的轉(zhuǎn)換方案我們將孔型分成9類即D,G，E，B，A,C，F(xiàn),H，F(xiàn),C，E,G,F，D,I，C,I,J。每一類型里面的孔在大的時(shí)候是沒(méi)有分先后順序的，如D,G這一類型中，D孔和G孔打得順序是無(wú)約束的，可以先打D孔也可以先打G孔還可

16、以打了一個(gè)D孔再打一個(gè)G孔再打一個(gè)D孔。對(duì)于，可以這樣考慮：（5-3）（5-4）其中：表示第k類孔的在給定的一種路線下轉(zhuǎn)頭的行進(jìn)的路程；表示i孔到j(luò)孔的距離；表示，否則不是在最優(yōu)路線上；是使個(gè)點(diǎn)能連成一條線；是對(duì)于第k類孔的一種優(yōu)化路徑下和第k+1類孔的一種優(yōu)化路徑下，第k類孔的最后一個(gè)點(diǎn)到第k+1類孔的第一個(gè)點(diǎn)的距離。5.2 模型求解5.2.1問(wèn)題一求解對(duì)于問(wèn)題一單鉆頭加工方式，鉆孔方式上采用一種刀具鉆完對(duì)應(yīng)的全部孔再轉(zhuǎn)換刀具進(jìn)行下一種刀具對(duì)其對(duì)應(yīng)孔型的鉆取方式，刀具轉(zhuǎn)換方案考慮到轉(zhuǎn)頭的個(gè)數(shù)不是很多，所以用窮舉法，而轉(zhuǎn)頭行進(jìn)路線則用模擬退火算法，通過(guò)MATLAB進(jìn)行數(shù)據(jù)處理和模型求解。求解步

17、驟：1、先對(duì)數(shù)據(jù)進(jìn)行處理，即將各種孔型的坐標(biāo)分別整理出來(lái)；2、根據(jù)模擬退火算法編寫(xiě)相應(yīng)程序，程序要求是只要給出起始點(diǎn)和各點(diǎn)坐標(biāo)，就能得到通過(guò)這些點(diǎn)的最優(yōu)路線，和對(duì)應(yīng)的總路程；3、打印出第一類孔（D孔和G孔）的分布圖如圖3根據(jù)分布圖可以看出右上角有一個(gè)點(diǎn)與其他點(diǎn)距離較大，所以我們就選這個(gè)點(diǎn)為起點(diǎn)（起點(diǎn)選擇原則一般就是與其他孔相聚較遠(yuǎn)的優(yōu)先考慮，也可以莫測(cè)一下可能的最優(yōu)路線，再根據(jù)得到的路線選擇起點(diǎn)），我們用MATLAB的圖形工具得到其坐標(biāo)為（3.122e+5,8.982e+5）如圖4圖3 D孔和G孔的分布圖圖4 用MATLAB的圖形工具得到右上角的點(diǎn)的坐標(biāo)4、運(yùn)用模擬退火算法得到優(yōu)化路線如圖5圖

18、5 D孔和G孔的優(yōu)化路線5、考慮到打完最后一個(gè)點(diǎn)之后就要進(jìn)行刀具切換，相鄰刀具的轉(zhuǎn)換時(shí)間是18s，在這18s內(nèi)，轉(zhuǎn)頭可以行進(jìn)180mm/s*18s=3240mm，所以下一類孔的起點(diǎn)如果考慮這個(gè)范圍內(nèi)，那么時(shí)間成本有很大的可能會(huì)降低，所以我們就以本類中的最后一個(gè)點(diǎn)為圓心，3240mm為半徑，畫(huà)出對(duì)應(yīng)的圓，再把下一類孔的分布圖也畫(huà)出來(lái)，然后根據(jù)下一類點(diǎn)的分布情況選擇起點(diǎn)，盡量考慮在剛才畫(huà)的圓內(nèi)，如圖6，我們選擇(-7.06e+4,4.91e+4)為第二類孔（E孔）的起點(diǎn)。圖6 D孔和G孔優(yōu)化路線、E孔的分布圖及其優(yōu)化路線的起始點(diǎn)6、以此類推，將9類孔的優(yōu)化路線都找出來(lái)（具體優(yōu)化路線見(jiàn)附錄），得到的

19、結(jié)果繪制成表格（表2）如下：表2 單轉(zhuǎn)頭9類孔對(duì)應(yīng)優(yōu)化路線的相關(guān)信息刀具種類加工孔型最短路程單位：mm起點(diǎn)坐標(biāo)單位：mil終點(diǎn)坐標(biāo)單位：mildDG1.4428e+005(3.122e+005,8.982e+005)(-1.3081e+003, 1.1201e+003)cE9.5507e+004(-7.060e+004,4.910e+004)(2.6467e+003, 1.9522e+004)bB2.8660e+005(9.230e+004,8.163e+005)(-1.9355e+003, 8.0213e+003)aAC3.2722e+005(-9.320e+004,3.264e+005)(

20、2.2555e+003, 4.3993e+003)hFH6.6242e+004(8.150e+004,6.070e+004)(2.3444e+003, 2.1262e+004)續(xù)表2 單轉(zhuǎn)頭9類孔對(duì)應(yīng)優(yōu)化路線的相關(guān)信息刀具種類加工孔型最短路程單位：mm起點(diǎn)坐標(biāo)單位：mil終點(diǎn)坐標(biāo)單位：milgFG6.1049e+004(2.13e+005,8.926e+005)(-7.6530e+003, -487.6800)fEGJ1.6314e+005(-3.013e+005,-1.92e+004)(4.6582e+003, 6.4890e+003)eDI1.3777e+005(1.690e+005,4.

21、170e+005)(6.1112e+003, 1.6822e+004)d無(wú)無(wú)無(wú)無(wú)cCIJ2.1903e+005(2.359e+005,6.274e+005)(-7.3406e+003, 1.7714e+004)單轉(zhuǎn)頭加工方式結(jié)果分析：刀具轉(zhuǎn)換總時(shí)間：刀具轉(zhuǎn)換總成本：刀具在各類孔中行進(jìn)的路程和：各類切換路程和：行進(jìn)總路程為：行進(jìn)總成本：總成本：總時(shí)間：5.2.2問(wèn)題二求解對(duì)于問(wèn)題二雙轉(zhuǎn)頭加工方式，我們要先找最優(yōu)分界線，即在線路板中找到一寬度為3cm的區(qū)域，使孔數(shù)關(guān)于該區(qū)域平分且區(qū)域內(nèi)沒(méi)有孔，則該區(qū)域的中線就是最優(yōu)分界線，再進(jìn)行求解，具體步驟為：1、我們先計(jì)算總數(shù)為2124個(gè)；2、再將孔的橫坐標(biāo)進(jìn)

22、行排序，得到第1062個(gè)和第1063個(gè)的橫坐標(biāo)，取其中點(diǎn)橫坐標(biāo)，則直線就是平分分界線，經(jīng)驗(yàn)證，該直線也是最優(yōu)分界線，所以就以直線為分界線，將孔平均分成兩部分；3、每一部分分別用問(wèn)題一的方法進(jìn)行求解，即得到問(wèn)題的解。（加工右邊的那個(gè)轉(zhuǎn)頭編號(hào)為1，加工左邊的編號(hào)為2）求解過(guò)程與問(wèn)題一相似，這里就不再重述了，將得到的結(jié)果繪制成表格（表3和表4）如下：表3 雙轉(zhuǎn)頭轉(zhuǎn)頭1加工9類孔對(duì)應(yīng)優(yōu)化路線的相關(guān)信息刀具種類加工孔型最短路程單位：mm起點(diǎn)坐標(biāo)單位：mil終點(diǎn)坐標(biāo)單位：mildDG0.7191e+005(3.122e+005,8.982e+005)(53200,60800)cE0.6838e+005(-

23、2.240e+004,4.910e+004)(104200,768600)bB1.2195e+005(9.230e+004,8.163e+005)(278400,5000)aAC1.8383e+005(3.294e+005,-6.52e+004)(3400,730000)hFH0.4481e+005(0.498e+005,7.569e+005)(165000,61300)gFG0.4433e+005(1.650e+005,6.130e+004)(173000,8926000)fEGJ1.1653e+005(1.020e+004,8.000e+005)(130600,301400)eDI0.83

24、51e+005(1.690e+005,4.170e+005)(22400,54000)d無(wú)無(wú)無(wú)無(wú)cCIJ1.4330e+005(-2.780e+004,1.633e+005)(22400,54000)雙轉(zhuǎn)頭加工方式轉(zhuǎn)頭1結(jié)果分析：刀具轉(zhuǎn)換總時(shí)間：刀具轉(zhuǎn)換總成本：刀具在各類孔中行進(jìn)的路程和：各類切換路程和：行進(jìn)總路程為：行進(jìn)總成本： 總成本：總時(shí)間：表4 雙轉(zhuǎn)頭轉(zhuǎn)頭2加工9類孔對(duì)應(yīng)優(yōu)化路線的相關(guān)信息刀具種類加工孔型最短路程單位：mm起點(diǎn)坐標(biāo)單位：mil終點(diǎn)坐標(biāo)單位：mildDG0.6362e+005(-4.150e+004,4.410e+004)(-257400,168770)cE0.4369e

25、+005(-2.832e+005,2.886e+005)(-271900,416500)續(xù)表4 雙轉(zhuǎn)頭轉(zhuǎn)頭2加工9類孔對(duì)應(yīng)優(yōu)化路線的相關(guān)信息刀具種類加工孔型最短路程單位：mm起點(diǎn)坐標(biāo)單位：mil終點(diǎn)坐標(biāo)單位：milbB1.3949e+005(-2.892e+005,4.340e+005)(-261000,746400)aAC1.2324e+005(-3.098e+005,9.080e+005)(-142200,274600)hFH0.1293e+005(-3.194e+005,4.565e+005)(-311300,-52400)gFG0.0878e+005(-3.113e+005,-5.24

26、0e+004)(-301300,64300)fEGJ0.6211e+005(-3.013e+005,6.430e+004)(-48400,723800)eDI0.5645e+005(-2.660e+005,8.690e+005)(-257400,184518)d無(wú)無(wú)無(wú)無(wú)cCIJ1.0582e+005(-2.960e+005,1.934e+005)(-257400,184518)雙轉(zhuǎn)頭加工方式轉(zhuǎn)頭2結(jié)果分析：刀具轉(zhuǎn)換總時(shí)間：刀具轉(zhuǎn)換總成本：刀具在各類孔中行進(jìn)的路程和：各類切換路程和：行進(jìn)總路程為：行進(jìn)總成本：總成本：總時(shí)間：雙轉(zhuǎn)頭加工方式結(jié)果分析：總成本：總時(shí)間：兩種作業(yè)方式比較見(jiàn)表5。表5 兩

27、種加工方式成本比較加工方式單轉(zhuǎn)頭雙轉(zhuǎn)頭效能提高(以單轉(zhuǎn)頭為基準(zhǔn))總成本95694元98239元-2.66%總時(shí)間2h22min1h24min+40.85%從表五可以看出，采用雙轉(zhuǎn)頭加工方式雖然成本上有增加，但增加很少，在誤差允許范圍內(nèi)可以忽略不計(jì)；而在時(shí)間上卻省下40%，所以雙轉(zhuǎn)頭方式效能更高，以時(shí)間計(jì)算，大約提高40%。5.2.3 研究打孔機(jī)的兩鉆頭合作間距對(duì)作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響由于打孔機(jī)的雙鉆頭合作間距會(huì)影響作業(yè)路線，合作間距控制不合理會(huì)浪費(fèi)資源，并且會(huì)導(dǎo)致兩個(gè)鉆頭不同時(shí)作業(yè)，使加工效率、加工質(zhì)量降低，增大作業(yè)成本，進(jìn)而影響到生產(chǎn)效能。所以必須選擇最合理的合作間距以提高工作效率和工

28、作質(zhì)量，進(jìn)而縮短作業(yè)成本，以達(dá)到提高生產(chǎn)效能目的。路徑的最優(yōu)是縮短鉆頭的加工路徑長(zhǎng)度來(lái)降低鉆頭移動(dòng)時(shí)間，其與間距的合理設(shè)置密切相關(guān)。所以，要提高生產(chǎn)效能，就要設(shè)置一個(gè)合理的合作間距。6 模型分析與評(píng)價(jià)該模型先得到最優(yōu)刀具轉(zhuǎn)換順序，再根據(jù)模擬退火算法得到各類孔的最優(yōu)作業(yè)路線，進(jìn)而得到問(wèn)題的解。得到的結(jié)果和預(yù)料的差不多，所以該模型的還是比較可靠的。該模型的優(yōu)點(diǎn)：1、將復(fù)雜問(wèn)題簡(jiǎn)單化。原問(wèn)題是要找到最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案），本模型就先找到最優(yōu)刀具轉(zhuǎn)換順序，再找最優(yōu)線路；而在找最優(yōu)線路的時(shí)候，又是根據(jù)最優(yōu)刀具轉(zhuǎn)換順序?qū)⒖走M(jìn)行分類，然后再每一類里找最優(yōu)線路。2、采用模擬退火算法進(jìn)行尋找最優(yōu)線路。

29、模擬退火算法廣泛應(yīng)用于優(yōu)化領(lǐng)域，從算法原理可以看出，理論上，當(dāng)降溫達(dá)到足夠緩慢，迭代次數(shù)達(dá)到足夠多，模擬退火算法是可以得到全局最優(yōu)解的。該模型也存在許多缺點(diǎn)和不足：1、先得到刀具最優(yōu)轉(zhuǎn)換順序再根據(jù)其進(jìn)行尋找最優(yōu)線路得到的結(jié)果不一定是全局最優(yōu)的。2、將孔型進(jìn)行分類，類與類之間的連接線路在全局上也不一定是最優(yōu)的。3、該問(wèn)題是尋找無(wú)回路的最優(yōu)線路，所以起點(diǎn)選擇會(huì)影響到解，誒本模型的起點(diǎn)選擇是由實(shí)驗(yàn)者目測(cè)和感覺(jué)確定的，所以也不一定是全局最優(yōu)的。4、模擬退火算法只是理論上能得到全局最優(yōu)解，實(shí)際上如果迭代次數(shù)太大或降溫太慢，則搜索時(shí)間需要很長(zhǎng)，效率很低，因此本模型得到的只是近似最優(yōu)解，而不是全局最優(yōu)解。5

30、、在解決雙轉(zhuǎn)頭作業(yè)方式時(shí)，是先得到一個(gè)解，再驗(yàn)證，如果不符合，再求解再驗(yàn)證，所以解決的效率很低。6、在雙轉(zhuǎn)頭作業(yè)方式中，該模型得到的解卻出現(xiàn)兩個(gè)轉(zhuǎn)頭作業(yè)時(shí)間不相等，也就是一個(gè)轉(zhuǎn)頭在工作，另一個(gè)轉(zhuǎn)頭卻在空閑，所以資源利用率沒(méi)有達(dá)到最高。參考文獻(xiàn)1 劉衛(wèi)國(guó).MATLAB程序設(shè)計(jì)與應(yīng)用(第二版).高等教育出版,2006.7(2010重印)2 打孔機(jī)生產(chǎn)效能的提高(優(yōu)秀論文).2012年12月27日.3 算法大全.現(xiàn)代優(yōu)化算法附錄A 單轉(zhuǎn)頭優(yōu)化路線圖（部分）圖A-1 E孔的優(yōu)化路線圖A-2 E孔優(yōu)化路線、B孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-3 B孔的優(yōu)化路線圖A-4 B孔的優(yōu)化路線、A孔和C孔的分布

31、圖及其優(yōu)化路線的起始點(diǎn)圖A-5 A孔和C孔的優(yōu)化路線圖A-6 A孔和C孔的優(yōu)化路線、F孔和H孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-7 F孔和H孔的優(yōu)化路線圖A-8 F孔和H孔的優(yōu)化路線、F孔和G孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-9 F孔和G孔的優(yōu)化路線圖A-10 F孔和G孔的優(yōu)化路線，E孔和G孔和J孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-11 E孔和G孔和J孔的優(yōu)化路線圖A-12 E孔和G孔和J孔的優(yōu)化路線，D孔和I孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-13 D孔和I孔的優(yōu)化路線圖A-14 D孔和I孔的優(yōu)化路線，C孔和I孔和J孔的分布圖及其優(yōu)化路線的起始點(diǎn)圖A-15 C孔和I孔和J孔的優(yōu)化路線附錄B

32、 MATLAB程序代碼（部分）1.數(shù)據(jù)處理1：fin=fopen('C1_data.txt','r');while(feof(fin) fp=fgetl(fin); if(length(fp) if(fp(1)='孔') %fclose(fout); switch(fp(5) case 'A' fout=fopen('A.txt','w'); case 'B' fout=fopen('B.txt','w'); case 'C' fout

33、=fopen('C.txt','w'); case 'D' fout=fopen('D.txt','w'); case 'E' fout=fopen('E.txt','w'); case 'F' fout=fopen('F.txt','w'); case 'G' fout=fopen('G.txt','w'); case 'H' fout=fopen(

34、9;H.txt','w'); case 'I' fout=fopen('I.txt','w'); case 'J' fout=fopen('J.txt','w'); end else fprintf(fout,'%srn',fp); end endendfclose(fin);fclose(fout);2.數(shù)據(jù)處理2：clear allfin=fopen('C1_data.txt','r');fout=fopen('Da

35、ta.txt','w');count=1;FP=;FPC=;while(feof(fin) fp=fgetl(fin); if(length(fp) if(fp(1)='孔') %fclose(fout); FP=FP,count; FPC=FPC,fp(5); else fprintf(fout,'%srn',fp); count=count+1; end endendcount=count-1;fclose(fin);fclose(fout);x X y Y=textread('Data.txt','%c %d

36、 %c %d');3.畫(huà)出所有孔的分布圖1：x Ax y Ay=textread('A.txt','%c %d %c %d');x Bx y By=textread('B.txt','%c %d %c %d');x Cx y Cy=textread('C.txt','%c %d %c %d');x Dx y Dy=textread('D.txt','%c %d %c %d');x Ex y Ey=textread('E.txt','%c

37、 %d %c %d');x Fx y Fy=textread('F.txt','%c %d %c %d');x Gx y Gy=textread('G.txt','%c %d %c %d');x Hx y Hy=textread('H.txt','%c %d %c %d');x Ix y Iy=textread('I.txt','%c %d %c %d');x Jx y Jy=textread('J.txt','%c %d %c %d&

38、#39;);plot(Ax,Ay,'b+')grid onhold onplot(Bx,By,'r+')plot(Cx,Cy,'g+')plot(Dx,Dy,'c+')plot(Ex,Ey,'m+')plot(Fx,Fy,'y+')plot(Gx,Gy,'k+')plot(Hx,Hy,'r.')plot(Ix,Iy,'b.')plot(Jx,Jy,'k.')legend('A','B','C

39、9;,'D','E','F','G','H','I','J');3.確定轉(zhuǎn)頭順序;%順序窮舉法查找=clear allB=1,3;3,6;4,7;7,6;5 3;6,3;for k=1:8 %k=1; for l=1:8 A(l)=mod(k+l-2,8)+1; end for i=1:6 m=min(find(A=B(i,1); n=max(find(A=B(i,2); if(n<m) alen=length(A); aend=A(end); while(A(end)=B(i

40、,2) alen=alen+1; A(alen)=mod(aend,8)+1; aend=A(end); end end end C(k)=length(A); clear A;endk=min(find(C=min(C);for l=1:8 A(l)=mod(k+l-2,8)+1;endfor i=1:6 m=min(find(A=B(i,1); n=max(find(A=B(i,2); if(n<m) alen=length(A); aend=A(end); while(A(end)=B(i,2) alen=alen+1; A(alen)=mod(aend,8)+1; aend=A(

41、end); end endendA%逆序窮舉法查找=clear allB=1,3;3,6;4,7;7,6;5 3;6,3;for k=1:8 %k=5; for l=1:8 A(l)=mod(7+k-l,8)+1; end for i=1:6 m=min(find(A=B(i,1); n=max(find(A=B(i,2); if(n<m) alen=length(A); aend=A(end); while(A(end)=B(i,2) alen=alen+1; A(alen)=mod(aend-1,8); if(A(end)=0) A(end)=8; end aend=A(end);

42、end end end C(k)=length(A); clear A;endk=min(find(C=min(C);for l=1:8 A(l)=mod(7+k-l,8)+1;endfor i=1:6 m=min(find(A=B(i,1); n=max(find(A=B(i,2); if(n<m) alen=length(A); aend=A(end); while(A(end)=B(i,2) alen=alen+1; A(alen)=mod(aend-1,8); if(A(end)=0) A(end)=8; end aend=A(end); end endendA4.模擬退火算法程

43、序：編寫(xiě)sa.m文件：%模擬退火算法(simulated annealing)%Sum,Path=sa(x0,y0,X,Y)%x0,y0：起點(diǎn)%X,Y:坐標(biāo)矩陣%Sum:總路程%Path:路徑function Sum,Path=sa(x0,y0,X,Y)X_mat=x0;X;Y_mat=y0;Y;Num=length(X_mat);MaxTime=9000000;Temper=1;EndTem=0.150;alpha=0.9999;%計(jì)算距離矩陣d=zeros(Num);for i=1:Num-1 for j=i:Num d(i,j)=sqrt(X_mat(i)-X_mat(j)2+(Y_ma

44、t(i)-Y_mat(j)2); endendd=(d+d')*0.0254;%產(chǎn)生初始解Path=;Sum=inf;for i=1:1000 S=1,1+randperm(Num-1); SumTemp=0; for j=1:Num-1 SumTemp=SumTemp+d(S(j),S(j+1); end if(SumTemp<Sum) Path=S; Sum=SumTemp; endend%模擬退火迭代for i=1:MaxTime c=sort(2+floor(Num-2)*rand(1,2); u=c(1);v=c(2); df=(d(Path(u-1),Path(v)+

45、d(Path(u),Path(v+1)-(d(Path(u-1),Path(u)+d(Path(v),Path(v+1); if(df<0) Path=Path(1:u-1),Path(v:-1:u),Path(v+1:Num); Sum=Sum+df; elseif(rand(1)<exp(-df/Temper) Path=Path(1:u-1),Path(v:-1:u),Path(v+1:Num); Sum=Sum+df; end Temper=Temper*alpha; if(Temper<EndTem) break; endend%畫(huà)出對(duì)應(yīng)優(yōu)化線路hold on;sj1=;for k=1:Num sj1=sj1;X_mat(Path(k),Y_mat(Path(k);endplot(sj1(:,1),sj1(:,2),'+-');hold off;end5.畫(huà)圓程序：編寫(xiě)circle.m文件：function circle(xCentre,yCentre,radius)seit