福建師范大學福清分校

1、20120806,福建師范大學福清分校數學與計算機科學系,打孔機生產效能的提高,學生: 李欣兒 王偉杰 楊 京 指導老師: 林 娟 福建師范大學福清分校數學與計算機科學系,20120806,福建師范大學福清分校數學與計算機科學系,問題重述,1. 單鉆頭的孔群加工2. 雙鉆頭的孔群加工,目標：提高打孔機的生產效能,刀具的旋轉方向,基本要

2、素：相鄰刀具的旋轉時間：18s鉆頭的移動速度：180mm/s鉆頭的行進成本：0.06元/mm刀具轉換的時間成本：7元/min,,兩鉆頭合作間距,20120806,福建師范大學福清分校數學與計算機科學系,影響打孔機的生產效能的因素： 1. 單個過孔的鉆孔作業(yè)時間2. 鉆頭的行進時間3. 刀具的轉換時間注意: 因為同一孔型鉆孔作業(yè)時間都是相同且刀具旋轉一次所花費的時間遠大于鉆頭在任意兩孔之間的行進時間，所以要提高

3、打孔機的生產效能首先我們考慮減少刀具的轉換時間(即減少刀具的轉換次數)其次考慮各個刀具所要打孔型點的最優(yōu)路線。,問題分析,20120806,福建師范大學福清分校數學與計算機科學系,1. 影響刀具轉換方案的因素：刀具的順序固定，不能調換刀具可順時針和逆時針旋轉有的孔型需要多種刀具及規(guī)定的加工次序來完成如：C(a,c),E(c,f),G(d,g,f),I(e,c),J(f,c) 因為f,c及c,f有順序,顯然易知會出

4、現f-c-f或c-f-c的情況,最少轉換次數大于等于8,且以c或f為開頭時可能為8。 由d g f的順序可知,以c或f開頭時,最小轉換次數大于8. 最優(yōu)的刀具轉換方案： d(D,G) — c(E)—b(B)—a(A,C)—h(F,H)—g(F,G) —f(E,G,J) — e(D,I)—c(C,I,J) 最小轉換次數:9,刀具轉換方案（單鉆頭）,20120806,福建師范大學福清分校數學與計算機科學系,孔

5、群加工最優(yōu)作業(yè)路線,我們將最優(yōu)的刀具方案的各個刀具視為一個模塊在求各個以刀具為模塊的最短路徑時,可將問題看作類TSP問題(注意:遍歷所有點后不回到原點) 在連接以刀具為模塊的各個模塊時可看作TSP問題(注意:遍歷所有點回到原點)中求得的最優(yōu)路線去掉此最優(yōu)路線中相鄰兩點最大距離的連線,20120806,福建師范大學福清分校數學與計算機科學系,刀具轉換方案和最優(yōu)作業(yè)路線（雙鉆頭）,1. 影響刀具轉換方案的因素：單鉆頭孔群加工時

6、包含的所有因素雙鉆頭各自完成的時間2. 孔群加工的最優(yōu)作業(yè)路線兩鉆頭的合作間距兩鉆頭路線同時變化固定長的一個鉆頭的路線,變化另一個鉆頭的路線路線中是否存在等待時間如: c刀具與f刀具,20120806,福建師范大學福清分校數學與計算機科學系,模型假設（1）假設打孔時的時間過小可忽略不計；（2）假設打孔時所耗效能忽略不計；（3）假設不出現斷電或器具損壞問題； （4）假設打孔后的等待時間極短可忽略不計；（5）假設將

7、鉆頭看作質點,20120806,福建師范大學福清分校數學與計算機科學系,問題描述：有 n個城市,其相互間距離d為已知, 求合理的路線使得每城市都訪問一次,且總路徑為最短。TSP的數學模型如下所示:,,TSP(旅行商問題),20120806,福建師范大學福清分校數學與計算機科學系,解決TSP問題的方法,貪心算法模擬退火算法改進的蟻群算法CONCORDE軟件,20120806,福建師范大學福清分校數學與計算機科學系,算法簡介,模

8、擬退火算法:是模擬物理的退火過程。退火是指將固體加熱到足夠高的溫度,使分子呈隨機排列狀態(tài),然后逐步降溫使之冷 卻,最后分子以低能狀態(tài)排列,固體達到某 種穩(wěn)定狀態(tài)。 蟻群算法:是模擬自然界螞蟻尋找食物時在所經過的路徑上留下一種揮發(fā)性的物質 (稱為信息素), 從而引導后續(xù)螞蟻走最短路徑提出的一種算法。,20120806,福建師范大學福清分校數學與計算機科學系,設最優(yōu)轉換方案的刀具集合:,最優(yōu)作業(yè)路線的模型,每一個刀具所需打

9、孔的個數:,各個刀具的最優(yōu)路線的孔的坐標集:,總最優(yōu)作業(yè)路線的最短路程：D,20120806,福建師范大學福清分校數學與計算機科學系,計算結果（單鉆頭）,,20120806,福建師范大學福清分校數學與計算機科學系,結果分析（單鉆頭）,以上兩種方法它們具有以下兩個共同特點:①該類方法都是從若干解出發(fā),通過對其鄰域的不斷搜索和當前解的替換來實現優(yōu)化,一次能夠處理大量模式,而且不受搜索空間連續(xù)性的限制;②該類方法都是在全空間并行搜索,且設

10、有跳出局部最優(yōu)的機制,具有較強的全局搜索能力。不同點：蟻群算法的搜索能力比模擬退火算法強,20120806,福建師范大學福清分校數學與計算機科學系,雙鉆頭孔群最優(yōu)路徑模型,假設兩個鉆頭的最優(yōu)路線的時間分別為T1和T2,則雙鉆頭孔群加工路線優(yōu)化的目標函數為: 約束條件: 任意一個待加工的孔必須包括在其中一條加工路徑中,且加工過程中兩個鉆頭不發(fā)生碰撞。,20120806,福建師范大學福清

11、分校數學與計算機科學系,雙鉆頭孔群的合作間距模型,20120806,福建師范大學福清分校數學與計算機科學系,雙鉆頭的最優(yōu)轉換方案,刀具轉換A方案：3-3（由于cf與fc相互制約的關系3-3變成了4-3）,刀具轉換B方案：4-3,注意：根據單鉆頭中得到結果可估計出B方案優(yōu)于A方案，但以下雙鉆頭的計算過程是根據A方案進行的一系列處理。,20120806,福建師范大學福清分校數學與計算機科學系,雙鉆頭孔群加工的分析和計算過程分析步驟：　　

12、確定哪個鉆頭的最優(yōu)路線不變,哪個鉆頭的最優(yōu)路線變化根據f1(J)與c2(J)之前的時間和的大小關系來判斷。2. 處理e(D,I)-> d(D,G) ->c1(C,E,I)的最優(yōu)路徑問題。 因為f1(J)與c2(J)制約的關系,要使時間作業(yè)成本更小, 首先先確定f1(J)與c2(J)應保持的間隔才避免不碰撞。 接著考慮 雙鉆頭不互相干擾的基礎上 e(D,I)-> d(D,G)

13、 ->c1(C,E,I)倒過來的最優(yōu)化作業(yè)路線。 (因為cf與fc刀具相互制約的關系, 可以把f(E,G,J)分為f1(J)和f2(E,G), c(E,C,I,J)分為c1(C,E,I)和c2(J), 且要求f1(J)要先于c2(J)完成。),20120806,福建師范大學福清分校數學與計算機科學系,3. 處理 f1(J)與c2(J)的最優(yōu)路徑問題： 已知: f1(J)要先于c2(J)完成,且受合作間距的影響。

14、 目標: 完成f1(J),c2(J)所花總時間最少即所間隔的 時間T(f1c2)最短 4. 總時間的計算:若更新后的e(D,I) ->d(D,G) -> c1(C,E,I)的時間和小于a(C,A) ->h(H,F)-> g(G,F)的時間和,則: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning否則(此處先不作考慮)5. 生產效能的計算: 生產效能提高

15、 =(單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間6. 作業(yè)成本的計算 : 作業(yè)成本 = 移動成本 + 旋轉成本,20120806,福建師范大學福清分校數學與計算機科學系,經計算得出由f1(j)與c2(j)之前的時間和分別為81.12s 和67.48s比較得知a(C,A) -> h(H,F)->g(G,F) -> f1(j)的最短路徑不改變.e(D,I) -> d(D,G)->c1(C,E,

16、I)的路線受雙鉆頭的合作間距的影響而改變。2. 由圖1可知,因為c2-d-e的路線與f1-g-h-a中旋轉時間的重復部分很多,重新計算的優(yōu)化路徑只有c2,d與e中的一部分數據。其中c2與f1中的部分的點(由3中可知只有兩個點的坐標)時間有可能重疊(計算得知c2的最優(yōu)路徑并沒改變)。而d中需要優(yōu)化的點從f1-g-h-a第二次旋轉結束時間開始,e中的點從f1-g-h-a第3次旋轉結束時間開始。,計算過程,20120806,福建師范大學福

17、清分校數學與計算機科學系,圖1:從J(f)處逆序開始雙鉆頭路線各個刀具的路程圖,,,可能產生碰撞的e與a區(qū)域,可能產生碰撞d與h區(qū)域,,紅黑曲線是旋轉時間所能移動的路程,20120806,福建師范大學福清分校數學與計算機科學系,并用鄰近交換算法計算得到路徑變化后的d'和e'如圖2,3所示,圖2 左圖為單鉆頭作業(yè)d刀具在D,G孔型處的最優(yōu)化路徑圖(需要變化部分) 右圖為雙鉆頭作業(yè)d刀具在D,G孔型處滿足合作間

18、距的新路徑圖,20120806,福建師范大學福清分校數學與計算機科學系,圖3 左圖為單鉆頭作業(yè)e刀具在D,I孔型處的最優(yōu)化路徑圖(需要變化部分) 右圖為雙鉆頭作業(yè)e刀具在D,I孔型處滿足合作間距的新路徑圖,20120806,福建師范大學福清分校數學與計算機科學系,3. 根據合作間距的限制求的f刀具與c刀具最小的間隔為153mm,即 在出發(fā)153/180s后再出發(fā),可保證雙鉆頭互相不干擾。4. 由以上計算可知,作業(yè)的總時間比

19、沒有隨著d-e中路徑的改變而發(fā)生變化。 Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning = 20.29+3.47+3.36+1097.48/180+153/180+18.19+4*18 =124.257s 5. 生產效能提高 = (單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間 = (250.181-124.257)/250.181

20、 = 0.4973= 49.73%,20120806,福建師范大學福清分校數學與計算機科學系,6. 作業(yè)成本作業(yè)成本 = 移動成本1 + 旋轉成本+移動成本2(刀具旋轉時移動） = (124.257-18*4)s*0.06元/mm*180mm/s+7/60元/s*18s*6+575.041mm*0.06元/mm = 611.47元其中e,d路徑變更時并沒有改變路徑的開始孔與結束孔的坐標編號

21、則最優(yōu)路徑中各刀具的開始孔與結束孔的坐標編號如下:(D145,d,D123,d),(E51,c,E40,c),(B740,b,B568,b),(C206,a,C166,a),(F14,h,H2,h),(G20,g,F27,g),(J24,f,E51,f),(D21,e, D135,e),(C177,c,C231,c),20120806,福建師范大學福清分校數學與計算機科學系,A. 兩鉆頭合作間距對作業(yè)路線的影響,合作間距 = 3

22、cm :1. 對d中點的影響: d中受影響部分的點的路程共有226 mm從d40= 185.292mm變到d’40 =249.085mm路程差d =d’40 –d40 = 53.8mm2. 對e中點的影響: e中受影響部分的點的路程共有452.8mm從 e87= 452.11mm變到e’87 =519.03mm。路程差 e=e’87 – e87 = 66.90mm 由數據得知兩變化的路徑所花費的時間和不足1s.,,201

23、20806,福建師范大學福清分校數學與計算機科學系,合作間距的影響,20120806,福建師范大學福清分校數學與計算機科學系,B. 兩鉆頭合作間距對生產效能的影響生產效能提高 = (單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間*100%雙鉆頭的作業(yè)時間: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning 其中受合作間距影響的只有 Tf1c2,而Tf1c2由鉆頭在J處的

24、最小間隔所決定且是一定的所以兩鉆頭合作間距并沒有對生產效能產生影響。,20120806,福建師范大學福清分校數學與計算機科學系,結論,解決TSP問題時，蟻群算法的搜索能力比模擬退火算法強。使用雙鉆頭能大大提高生產效能將近五成(計算結果為49.73%)。合作間距對作業(yè)路線產生微小變化,對生產效能的提高影響不大。注：此次雙鉆頭采取的并不是 最優(yōu)刀具轉化方案下得出的結果。,20120806,福建師范大學福清分校數學與計