打孔機生產(chǎn)效能的提高課件.ppt

20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,打孔機生產(chǎn)效能的提高,學(xué)生: 李欣兒 王偉杰 楊 京 指導(dǎo)老師: 林 娟 福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,問題重述,1. 單鉆頭的孔群加工 2. 雙鉆頭的孔群加工,目標：提高打孔機的生產(chǎn)效能,刀具的旋轉(zhuǎn)方向,基本要素： 相鄰刀具的旋轉(zhuǎn)時間：18s 鉆頭的移動速度：180mm/s 鉆頭的行進成本：0.06元/mm 刀具轉(zhuǎn)換的時間成本：7元/min,兩鉆頭合作間距,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,影響打孔機的生產(chǎn)效能的因素： 1. 單個過孔的鉆孔作業(yè)時間 2. 鉆頭的行進時間 3. 刀具的轉(zhuǎn)換時間 注意: 因為同一孔型鉆孔作業(yè)時間都是相同且刀具旋轉(zhuǎn)一次所花費的 時間遠大于鉆頭在任意兩孔之間的行進時間，所以要提高打孔 機的生產(chǎn)效能首先我們考慮減少刀具的轉(zhuǎn)換時間(即減少刀 具的轉(zhuǎn)換次數(shù))其次考慮各個刀具所要打孔型點的最優(yōu)路線。,問題分析,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,1. 影響刀具轉(zhuǎn)換方案的因素： 刀具的順序固定，不能調(diào)換 刀具可順時針和逆時針旋轉(zhuǎn) 有的孔型需要多種刀具及規(guī)定的加工次序來完成 如：C(a,c),E(c,f),G(d,g,f),I(e,c),J(f,c) 因為f,c及c,f有順序,顯然易知會出現(xiàn)f-c-f或c-f-c的情況,最少轉(zhuǎn)換次數(shù)大于等于8,且以c或f為開頭時可能為8。 由d g f的順序可知,以c或f開頭時,最小轉(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é)與計算機科學(xué)系,孔群加工最優(yōu)作業(yè)路線,我們將最優(yōu)的刀具方案的各個刀具視為一個模塊 在求各個以刀具為模塊的最短路徑時,可將問題看作 類TSP問題(注意:遍歷所有點后不回到原點) 在連接以刀具為模塊的各個模塊時可看作TSP問題(注意:遍歷所有點回到原點)中求得的最優(yōu)路線去掉此最優(yōu)路線中相鄰兩點最大距離的連線,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,刀具轉(zhuǎn)換方案和最優(yōu)作業(yè)路線（雙鉆頭）,1. 影響刀具轉(zhuǎn)換方案的因素： 單鉆頭孔群加工時包含的所有因素 雙鉆頭各自完成的時間 2. 孔群加工的最優(yōu)作業(yè)路線 兩鉆頭的合作間距 兩鉆頭路線同時變化 固定長的一個鉆頭的路線,變化另一個鉆頭的路線 路線中是否存在等待時間如: c刀具與f刀具,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,模型假設(shè) （1）假設(shè)打孔時的時間過小可忽略不計； （2）假設(shè)打孔時所耗效能忽略不計； （3）假設(shè)不出現(xiàn)斷電或器具損壞問題； （4）假設(shè)打孔后的等待時間極短可忽略不計； （5）假設(shè)將鉆頭看作質(zhì)點,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,問題描述：有 n個城市,其相互間距離d為已知, 求合理的路線使得每城市都訪問一次,且總路徑為最短。 TSP的數(shù)學(xué)模型如下所示:,TSP(旅行商問題),20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,解決TSP問題的方法,貪心算法 模擬退火算法 改進的蟻群算法 CONCORDE軟件,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,算法簡介,模擬退火算法:是模擬物理的退火過程。退火是指將固體加熱到足夠高的溫度,使分子呈隨機排列狀態(tài),然后逐步降溫使之冷 卻,最后分子以低能狀態(tài)排列,固體達到某 種穩(wěn)定狀態(tài)。 蟻群算法:是模擬自然界螞蟻尋找食物時在所經(jīng)過的路徑上留下一種揮發(fā)性的物質(zhì) (稱為信息素), 從而引導(dǎo)后續(xù)螞蟻走最短路徑提出的一種算法。,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,設(shè)最優(yōu)轉(zhuǎn)換方案的刀具集合:,最優(yōu)作業(yè)路線的模型,每一個刀具所需打孔的個數(shù):,各個刀具的最優(yōu)路線的孔的坐標集:,總最優(yōu)作業(yè)路線的最短路程：D,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,計算結(jié)果（單鉆頭）,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,結(jié)果分析（單鉆頭）,以上兩種方法它們具有以下兩個共同特點: 該類方法都是從若干解出發(fā),通過對其鄰域的不斷搜索和當前解的替換來實現(xiàn)優(yōu)化,一次能夠處理大量模式,而且不受搜索空間連續(xù)性的限制; 該類方法都是在全空間并行搜索,且設(shè)有跳出局部最優(yōu)的機制,具有較強的全局搜索能力。 不同點： 蟻群算法的搜索能力比模擬退火算法強,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,雙鉆頭孔群最優(yōu)路徑模型,假設(shè)兩個鉆頭的最優(yōu)路線的時間分別為T1和T2 ,則雙鉆頭孔群加工路線優(yōu)化的目標函數(shù)為: 約束條件: 任意一個待加工的孔必須包括在 其中一條加工路徑中,且加工過程中兩個鉆頭 不發(fā)生碰撞。,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,雙鉆頭孔群的合作間距模型,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(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é)果可估計出B方案優(yōu)于A方案， 但以下雙鉆頭的計算過程是根據(jù)A方案進行的一系列處理。,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,雙鉆頭孔群加工的分析和計算過程 分析步驟： 確定哪個鉆頭的最優(yōu)路線不變,哪個鉆頭的最優(yōu)路線變化根據(jù)f1(J)與c2(J)之前的時間和的大小關(guān)系來判斷。 2. 處理e(D,I)- d(D,G) -c1(C,E,I)的最優(yōu)路徑問題。 因為f1(J)與c2(J)制約的關(guān)系,要使時間作業(yè)成本更小, 首先先確定f1(J)與c2(J)應(yīng)保持的間隔才避免不碰撞。 接著考慮 雙鉆頭不互相干擾的基礎(chǔ)上 e(D,I)- d(D,G) -c1(C,E,I)倒過來的最優(yōu)化作業(yè)路線。 (因為cf與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é)與計算機科學(xué)系,3. 處理 f1(J)與c2(J)的最優(yōu)路徑問題： 已知: f1(J)要先于c2(J)完成,且受合作間距的影響。 目標: 完成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. 生產(chǎn)效能的計算: 生產(chǎn)效能提高 =(單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間 6. 作業(yè)成本的計算 : 作業(yè)成本 = 移動成本 + 旋轉(zhuǎn)成本,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,經(jīng)計算得出由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,I)的路線受雙鉆頭的合作間距的影響而改變。 2. 由圖1可知,因為c2-d-e的路線與f1-g-h-a中旋轉(zhuǎn)時間的重復(fù)部分很多,重新計算的優(yōu)化路徑只有c2,d與e中的一部分數(shù)據(jù)。其中c2與f1中的部分的點(由3中可知只有兩個點的坐標)時間有可能重疊(計算得知c2的最優(yōu)路徑并沒改變)。而d中需要優(yōu)化的點從f1-g-h-a第二次旋轉(zhuǎn)結(jié)束時間開始,e中的點從f1-g-h-a第3次旋轉(zhuǎn)結(jié)束時間開始。,計算過程,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,圖1:從J(f)處逆序開始雙鉆頭路線各個刀具的路程圖,可能產(chǎn)生碰撞的e與a區(qū)域,可能產(chǎn)生碰撞d與h區(qū)域,紅黑曲線是旋轉(zhuǎn)時間所能移動的路程,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,并用鄰近交換算法計算得到路徑變化后的d和e如圖2,3所示,圖2 左圖為單鉆頭作業(yè)d刀具在D,G孔型處的最優(yōu)化路徑圖(需要變化部分) 右圖為雙鉆頭作業(yè)d刀具在D,G孔型處滿足合作間距的新路徑圖,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,圖3 左圖為單鉆頭作業(yè)e刀具在D,I孔型處的最優(yōu)化路徑圖(需要變化部分) 右圖為雙鉆頭作業(yè)e刀具在D,I孔型處滿足合作間距的新路徑圖,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,3. 根據(jù)合作間距的限制求的f刀具與c刀具最小的間隔為153mm,即 在出發(fā)153/180s后再出發(fā),可保證雙鉆頭互相不干擾。 4. 由以上計算可知,作業(yè)的總時間比沒有隨著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)效能提高 = (單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間 = (250.181-124.257)/250.181 = 0.4973= 49.73%,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,6. 作業(yè)成本 作業(yè)成本 = 移動成本1 + 旋轉(zhuǎn)成本+移動成本2(刀具旋轉(zhuǎn)時移動） = (124.257-18*4)s*0.06元/mm*180mm/s +7/60元/s*18s*6+575.041mm*0.06元/mm = 611.47元 其中e,d路徑變更時并沒有改變路徑的開始孔與結(jié)束 孔的坐標編號則最優(yōu)路徑中各刀具的開始孔與結(jié)束 孔的坐標編號如下: (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é)與計算機科學(xué)系,A. 兩鉆頭合作間距對作業(yè)路線的影響,合作間距 = 3cm : 1. 對d中點的影響: d中受影響部分的點的路程共有 226 mm從d40= 185.292mm變到d40 =249.085mm 路程差d =d40 d40 = 53.8mm 2. 對e中點的影響: e中受影響部分的點的路程共有452.8mm從 e87= 452.11mm變到e87 =519.03mm。路程差 e=e87 e87 = 66.90mm 由數(shù)據(jù)得知兩變化的路徑所花費的時間和不足1s.,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,合作間距的影響,20120806,福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系,B. 兩鉆頭合作間距對生產(chǎn)效能的影響 生產(chǎn)效能提高 = (單一鉆頭花費的時間-雙鉆頭花費的時間)/單一鉆頭花費的時間*100% 雙鉆頭的作業(yè)時間: Ttotal=Ta+Th+Tg+Tf1+Tf1c2+Tb+4*Tturning 其中受合作間距影