福建師范大學(xué)福清分校

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

2、素：相鄰刀具的旋轉(zhuǎn)時(shí)間：18s鉆頭的移動(dòng)速度：180mm/s鉆頭的行進(jìn)成本：0.06元/mm刀具轉(zhuǎn)換的時(shí)間成本：7元/min,,兩鉆頭合作間距,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,影響打孔機(jī)的生產(chǎn)效能的因素： 1. 單個(gè)過孔的鉆孔作業(yè)時(shí)間2. 鉆頭的行進(jìn)時(shí)間3. 刀具的轉(zhuǎn)換時(shí)間注意: 因?yàn)橥豢仔豌@孔作業(yè)時(shí)間都是相同且刀具旋轉(zhuǎn)一次所花費(fèi)的時(shí)間遠(yuǎn)大于鉆頭在任意兩孔之間的行進(jìn)時(shí)間，所以要提高

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

4、現(xiàn)f-c-f或c-f-c的情況,最少轉(zhuǎn)換次數(shù)大于等于8,且以c或f為開頭時(shí)可能為8。 由d g f的順序可知,以c或f開頭時(shí),最小轉(zhuǎn)換次數(shù)大于8. 最優(yōu)的刀具轉(zhuǎn)換方案： 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) 最小轉(zhuǎn)換次數(shù):9,刀具轉(zhuǎn)換方案（單鉆頭）,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,孔

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

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

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

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

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

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

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

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

13、 ->c1(C,E,I)倒過來的最優(yōu)化作業(yè)路線。 (因?yàn)閏f與fc刀具相互制約的關(guān)系, 可以把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,福建師范大學(xué)福清分校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,3. 處理 f1(J)與c2(J)的最優(yōu)路徑問題： 已知: f1(J)要先于c2(J)完成,且受合作間距的影響。

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

15、 =(單一鉆頭花費(fèi)的時(shí)間-雙鉆頭花費(fèi)的時(shí)間)/單一鉆頭花費(fèi)的時(shí)間6. 作業(yè)成本的計(jì)算 : 作業(yè)成本 = 移動(dòng)成本 + 旋轉(zhuǎn)成本,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,經(jīng)計(jì)算得出由f1(j)與c2(j)之前的時(shí)間和分別為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可知,因?yàn)閏2-d-e的路線與f1-g-h-a中旋轉(zhuǎn)時(shí)間的重復(fù)部分很多,重新計(jì)算的優(yōu)化路徑只有c2,d與e中的一部分?jǐn)?shù)據(jù)。其中c2與f1中的部分的點(diǎn)(由3中可知只有兩個(gè)點(diǎn)的坐標(biāo))時(shí)間有可能重疊(計(jì)算得知c2的最優(yōu)路徑并沒改變)。而d中需要優(yōu)化的點(diǎn)從f1-g-h-a第二次旋轉(zhuǎn)結(jié)束時(shí)間開始,e中的點(diǎn)從f1-g-h-a第3次旋轉(zhuǎn)結(jié)束時(shí)間開始。,計(jì)算過程,20120806,福建師范大學(xué)福

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

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

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. 生產(chǎn)效能提高 = (單一鉆頭花費(fèi)的時(shí)間-雙鉆頭花費(fèi)的時(shí)間)/單一鉆頭花費(fèi)的時(shí)間 = (250.181-124.257)/250.181

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

21、則最優(yōu)路徑中各刀具的開始孔與結(jié)束孔的坐標(biāo)編號(hào)如下:(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,福建師范大學(xué)福清分校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,A. 兩鉆頭合作間距對(duì)作業(yè)路線的影響,合作間距 = 3

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

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

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