（機(jī)械設(shè)計(jì)及理論專業(yè)論文）柔性制造系統(tǒng)刀具流動(dòng)態(tài)調(diào)度研究.pdf

柔性制造系統(tǒng)刀具流動(dòng)態(tài)調(diào)度研究 摘要 刀具流調(diào)度是柔性制造系統(tǒng)( f m s ) 調(diào)度的重要組成部分，f m s 的生產(chǎn)效率和 系統(tǒng)柔性在很大程度上取決于刀具流的合理規(guī)劃。當(dāng)前刀具流的調(diào)度理論與算法還十 分有限，實(shí)際運(yùn)行中的刀具流自動(dòng)化水平也較低，這種現(xiàn)狀已經(jīng)在較大程度上影響了 f m s 生產(chǎn)能力的進(jìn)一步發(fā)揮，因此，為了提高系統(tǒng)的總體加工性能和充分發(fā)揮f m s 本身的柔性，進(jìn)行更深入的刀具流調(diào)度研究具有重要的理論價(jià)值和實(shí)際意義。 本文以f m s 中刀具流調(diào)度為研究對(duì)象，分析了刀具流動(dòng)態(tài)調(diào)度研究的必要性， 回顧了刀具流調(diào)度理論的研究現(xiàn)狀，研究了f m s 生產(chǎn)中工序備刀與工步備刀兩種情 況下的刀具流調(diào)度問題，并對(duì)刀具流調(diào)度過程中的死鎖檢測和死鎖避免等關(guān)鍵技術(shù)問 題進(jìn)行了深入分析。 首先，結(jié)合面向?qū)ο蠹夹g(shù)和p e t r i 網(wǎng)理論分別為f m $ 生產(chǎn)中的工序備刀情況和工 步備刀情況建立了調(diào)度仿真模型。該模型不僅包括了工件流，同時(shí)還重點(diǎn)考慮了刀具 流進(jìn)程，并將機(jī)床故障與刀具失效作為一個(gè)組成部分包括進(jìn)來，從而準(zhǔn)確方便地描述 了考慮刀具流的f m s 運(yùn)行各個(gè)環(huán)節(jié)，為后續(xù)的刀具流啟發(fā)式調(diào)度研究奠定了基礎(chǔ)。 其次，在以往工序備刀前提下的刀具流無死鎖調(diào)度工作基礎(chǔ)上，進(jìn)一步將刀具壽 命考慮進(jìn)來，從而豐富和完善了現(xiàn)有刀具流相關(guān)調(diào)度理論與技術(shù)。采用圖論方法建立 了擴(kuò)展的刀具申請(qǐng)分配圖，并將其和刀具流死鎖聯(lián)系起來，從圖論角度深刻揭示了刀 具流死鎖本質(zhì)。在擴(kuò)展的刀具申請(qǐng)分配圖基礎(chǔ)上，建立了刀具流死鎖判定定理和非死 鎖圖的性質(zhì)定理。提出了兩層死鎖避免策略，分別用于機(jī)床選工序和刀具分派兩模塊 的死鎖控制，實(shí)例分析表明了該策略的合理性和可行性。 在刀具分派決策中充分考慮了刀具流對(duì)工件流效率的影響，提出了目標(biāo)機(jī)床當(dāng)前 加工完成時(shí)間最早規(guī)則。實(shí)驗(yàn)結(jié)果表明該規(guī)則能夠有效地減少機(jī)床的刀具等待時(shí)間， 提高了系統(tǒng)的生產(chǎn)效率。將兩層死鎖避免策略與調(diào)度規(guī)則相結(jié)合，最終建立了工序備 刀下的刀具流無死鎖啟發(fā)式調(diào)度算法，并給出了刀具失效的處理策略，仿真結(jié)果表明 了該算法的有效性。 在完成了工序備刀下的刀具流研究之后，基于圖論方法深入研究了工步備刀前提 下刀具流的無死鎖調(diào)度問題。建立了刀具流狀態(tài)演變模型，給出了刀具流死鎖狀態(tài)及 無死鎖不安全狀態(tài)的定義。構(gòu)建了刀具資源分派圖并提出了機(jī)床死鎖的概念，將機(jī)床 死鎖與刀具流的無死鎖不安全狀態(tài)有機(jī)聯(lián)系起來，設(shè)計(jì)了一種刀具流無死鎖不安全狀 態(tài)檢測算法，并在此基礎(chǔ)上進(jìn)一步給出了刀具流的死鎖避免方法。實(shí)例表明該方法能 夠簡單有效地避免死鎖的產(chǎn)生。 在刀具分派決策研究中提出了虛擬機(jī)床隊(duì)列思想，并將其與死鎖避免方法相結(jié) 合，最終構(gòu)建了工步備刀下的刀具流無死鎖啟發(fā)式調(diào)度算法，并對(duì)調(diào)度過程中的刀具 哈爾溟t 稗大學(xué)博十學(xué)何論文 失效給出了相應(yīng)的處理策略，解決了工步備刀下的刀具流死鎖避免和刀具實(shí)時(shí)分派問 題。 在完成了工步備刀下的刀具流無死鎖啟發(fā)式調(diào)度研究之后，進(jìn)一步從全局優(yōu)化角 度分析了刀具流調(diào)度問題。以系統(tǒng)完工時(shí)間最少為優(yōu)化目標(biāo)，建立了工件流和刀具流 綜合調(diào)度數(shù)學(xué)模型。提出了一種雙重遺傳算法對(duì)優(yōu)化模型進(jìn)行求解：外層遺傳算法用 于求解可行工序加工序列；內(nèi)層遺傳算法用于最優(yōu)可行刀具分派方案的搜索。實(shí)例分 析表明了雙重遺傳算法的有效性和可行性。為使調(diào)度系統(tǒng)能夠有效處理機(jī)床故障和刀 具破損等突發(fā)事件的再調(diào)度問題，進(jìn)一步給出了一類基于雙重遺傳算法的準(zhǔn)靜態(tài)優(yōu)化 再調(diào)度方法。 最后，建立了各類算法的仿真調(diào)度程序，對(duì)各算法下系統(tǒng)的性能指標(biāo)進(jìn)行了比較 和綜合評(píng)價(jià)，仿真分析結(jié)果表明所建立的工序備刀下的啟發(fā)式調(diào)度算法和工步備刀下 的啟發(fā)式調(diào)度算法及優(yōu)化調(diào)度算法是可行而有效的。這些調(diào)度理論與算法的提出為 f m s 的設(shè)計(jì)和運(yùn)行提供了依據(jù)，為實(shí)際生產(chǎn)中f m s 性能的充分發(fā)揮奠定了基礎(chǔ)。 關(guān)鍵詞：柔性制造系統(tǒng)；刀具流；死鎖檢測；死鎖避免；雙重遺傳算法 柔性制造系統(tǒng)刀具流動(dòng)態(tài)調(diào)度研究 a b s t r a c t p r o d u c t i o ne f f i c i e n c ya n ds y s t e mf l e x i b i l i t yo ff l e x i b l em a n u f a c t u r i n gs y s t e m ( f m s ) a r em o s t l yd e p e n do nr e a s o n a b l ep l a n n i n gf o r t o o lf l o w , w h o s es c h e d u l ei so n eo fi m p o r t a n t e l e m e n t so ff m ss c h e d u l i n g b u tt h es t a t e - o f - t h e a r ts c h e d u l i n gt h e o r ya n da l g o r i t h mo f t o o l sf l o wa r en o ts oa d v a n c e dt h a tt h ed e g r e eo fa u t o m a t i o no ft o o l sf l o wi nj o bs h o pi s c o m p a r a t i v e l yl o w , w h i c hg r e a t l yr e s t r a i nt h ep r o d u c t i o na b i l i t yo ff m si n c r e a s i n g h e n c e ， f u r t h e rr e s e a r c ho np r o p e rp l a n n i n ga n ds c h e d u l i n gf o rt o o lf l o wi si m p e r a t i v ef r o mt h e v i e wo ft h e o r ya n dp r a c t i c ei no r d e rt oi m p r o v et h eo v e r a l ls y s t e mp r o d u c t i o na b i l i t ya n d m a k ef u l lo ft h ea d v a n t a g eo ff m si nf l e x i b i l i t y i nt h ec o u r s eo ft h et h e s i sp r e s e n t e d ，t h es u b j e c to fr e s e a r c hi st o o lf l o ws c h e d u l i n gi n f m se n v i r o n m e n t t h en e c e s s i t yo ft o o lf l o wd y n a m i cs c h e d u l i n gr e s e a r c hi ss t a t e d ，a n d t h es t a t eo ft h ea r to ft o o lf l o ws c h e d u l i n gt h e o r yi sr e v i e w e d t h e nt o o lf l o ws c h e d u l i n gi n c a s e so fp r o c e d u r ep r o v i s i o n i n gt o o l sa n dw o r k i n gs t e pp r o v i s i o n i n gt o o l sa r ei n v e s t i g a t e d ， a n dt h ed e a d l o c kd e t e c t i n ga n dd e a d l o c ka v o i d a n c ed u r i n gt h es c h e d u l eo ft o o lf l o wa r e d e e p l ya n a l y z e d f i r s t l y , s i m u l a t i o n m o d e l sa r e d e v e l o p e dr e s p e c t i v e l y i nc a s e so fp r o c e d u r e p r o v i s i o n i n gt o o l sa n dw o r k i n gs t e pp r o v i s i o n i n gt o o l sb a s e do i lp e t r in e tw i t ht h e o r i e n t e d - o b j e c tt e c h n i q u e t h em o d e l sd e v e l o p e da c c u r a t e l ya n dc o n v e n i e n t l yd e s c r i b ea l l t h es e c t i o n sw h e nf m si sr u n n i n gw i t hn o to n l yc o n s i d e r i n gt h ep a r tf l o wb u ta l s of o c u s i n g o nt h et o o lf l o w , a n di n c l u d et h em a c h i n em a l f u n c t i o na n dt o o lf a i l u r e 鶴ac o m p o n e n t t h i s i sb a s i cf o rt o o lf l o wh e u r i s t i cs c h e d u l i n g s e c o n d l y , c u t t i n gt o o l sl i f ei sc o n s i d e r e da saf a c t o rt or i c ha n de n h a n c et o o lf l o w s c h e d u l i n g t h e o r ya n dt e c h n i q u eb a s e do nt o o lf l o wd e a d l o c k - f r e es c h e d u l i n go nt h e c o n d i t i o no fp r o c e d u r ep r o v i s i o n i n gt o o l s e x t e n d e dt o o l sa p p l y i n ga l l o c a t i o ng r a p hi n r e l a t i o nt ot o o lf l o wd e a d l o c ks t r a t e g yi sb u i l tu pw i t ht h eg r a p ht h e o r y t h en a t u r eo ft o o l f l o wd e a d l o c ki sr e v e a l e dp r o f o u n d l yf r o mt h ev i e wo fg r a p ht h e o r y t o o lf l o wd e a d l o c k d e c i s i o nt h e o r e ma n dn o n d e a d l o c kg r a p hp r o p e r t yt h e o r e ma r eg i v e nb a s e do ne x t e n d e d t o o l sa p p l y i n ga l l o c a t i o ng r a p h d o u b l e l a y e rd e a d l o c ka v o i d a n c es t r a t e g yi s b r o u g h t f o r t ht op r e v e n td e a d l o c ki nt w om o d e l so fm a c h i n es e l e c t i o np r o c e s sa n dt o o l sa l l o c a t i o n t h ee f f e c to ft o o lf l o wo np a r tf l o we f f i c i e n c yi sf u l l yc o n s i d e r e di nt o o l sa l l o c a t i o n d e c i s i o n ，a n dt h er u l eo fe a r l i e s tf i n i s ht i m ef o rc u r r e n to p e r a t i o ni sg i v e n t h ee x p e r i m e n t r e s u l t ss h o wt h a tt h er u l ep r e s e n t e di sa b l et od e c e a s et h ew a i t i n gt i m ef o rt o o l se f f e c t i v e l y a n di m p r o v et h ep r o d u c t i o ne f f i c i e n c yo ft h es y s t e m t o o lf l o wd e a d l o c k - f r e eh e u r i s t i c s c h e d u l i n ga l g o r i t h mi nc a s eo fp r o c e d u r ep r o v i s i o n i n gt o o l si sb u i l tu pw i t ht h em e t h o do f 哈爾濱t 程大學(xué)博士學(xué)位論文 c o m b i n a t i o nd o u b l e - l a y e rd e a d l o c ka v o i d a n c es t r a t e g ya n ds c h e d u l i n gr u l e s ，a n dt h e h a n d l i n gt a c t i c so ft o o l sf a i l u r ea r eg i v e n t h es i m u l a t i o nr e s u l t ss h o w t h a tt h ea l g o r i t h mi s e f f e c t i v e t h e nt o o lf l o wd e a d l o c k f r e es c h e d u l i n gi nc a s eo fw o r k i n gs t e pp r o v i s i o n i n gt o o l s b a s e do ng r a p ht h e o r yi sr e s e a r c h e dd e e p l y t h ee v o l v i n gm o d e lo ft o o l sf l o ws t a t ei sb u i l t u p ，a n dt h es t a t e so ft o o l sf l o wd e a d l o c ka n dt o o l sf l o wd e a d l o c k f r e eu n s a f ea r ed e f i n e d t h et o o l sr e s o u r c ea l l o c a t i o ng r a p ha n dt h ed e f i n i t i o no fm a c h i n ed e a d l o c ka r eg i v e n c o m b i n e dm a c h i n ed e a d l o c kw i t ht o o l sf l o wd e a d l o c k - f r e eu n s a f es t a t e ，ad e t e c t i o n a l g o r i t h mo ft o o l sf l o wd e a d l o c k - f r e eu n s a f es t a t ei sd e s i g n e d ，b a s e do nw h i c ht h et o o l s f l o w d e a d l o c ka v o i d a n c ea p p r o a c hi sd e v e l o p e d a ne x a m p l es h o w st h i sa p p r o a c hi sa b l et o a v o i dt h eo c c u r r e n c eo ft o o l sf l o wd e a d l o c k t o o lf l o wd e a d l o c k f r e eh e u r i s t i cs c h e d u l i n ga l g o r i t h mi nc a s eo fw o r k i n gs t e p p r o v i s i o n i n gt o o l si sd e v e l o p e db a s e do nt h ev i r t u a lm a c h i n eq u e u ei d e aa n dt h ed e a d l o c k a v o i d a n c ea p p r o a c hi nt o o l sa l l o c a t i o nd e c i s i o n ，t h e nt h ec o r r e s p o n d i n gh a n d l i n gs t r a t e g y o ft o o l sf a i l u r ei nt h ep r o g r e s so fs c h e d u l i n gi sg i v e n t h u s ，t o o lf l o wd e a d l o c ka v o i d a n c e a n dt o o l sa l l o c a t i o ni nr e a lt i m ea r es o l v e di nc a s eo fw o r k i n gs t e pp r o v i s i o n i n gt o o l s t o o lf l o ws c h e d u l i n gi sa n a l y z e df r o mt h ev i e wo ft h eg l o b a lo p t i m i z a t i o n ，a f t e r r e s e a r c ho nt o o lf l o wd e a d l o c k - f r e eh e u r i s t i cs c h e d u l i n g am a t h e m a t i c a lm o d e lo f i n t e g r a t e ds c h e d u l i n gf o rp a r tf l o wa n dt o o lf l o wi sp r e s e n t e d ，i nw h i c h t h eo b j e c t i v ei st o m i n i m i z es y s t e mm a k e - s p a n ad o u b l e l a y e rg e n e t i ca l g o r i t h m ( g a ) i sp r o p o s e df o rg l o b a l o p t i m i z a t i o no ft h em o d e l t h eo u t e ra n di n n e rl a y e r so ft h eg a a r et os e a r c ho p t i m a la n d f e a s i b l eo p e r a t i o ns e q u e n c e sa n dt o o la s s i g n m e n t ，r e s p e c t i v e l y ac a s es t u d ys h o w st h a tt h e d o u b l e l a y e rg a i se f f e c t i v ea n dp r a c t i c a b l e t h eq u a s i s t a t i co p t i m a lr e s c h e d u l i n gb a s e o nd o u b l e l a y e rg ai sp r e s e n t e di no r d e rt od e a lw i t he f f e c t i v e l ye m e r g e n c i e ss u c ha s m a c h i n em a l f u n c t i o na n dt o o l sb r e a k a g e f i n a l l y , t h es c h e d u l i n gs i m u l a t i o np r o g r a m sb a s e do na l g o r i t h m sd e v e l o p e da r eg i v e n a n dt h es y s t e mp e r f o r m a n c ei n d e xb ym e a n so ft h ea l g o r i t h m s t h es i m u l a t i o nr e s u l t ss h o w t h a tt h eh e u r i s t i cs c h e d u l i n ga n do p t i m a ls c h e d u l i n ga l g o r i t h m si nc a s eo fp r o c e d u r e p r o v i s i o n i n gt o o l sa n dw o r k i n gs t e pp r o v i s i o n i n gt o o l sa r ef e a s i b l ea n de f f e c t i v e l y t h e p r e s e n t e ds c h e d u l i n gt h e o r ya n da l g o r i t h mp r o v i d eaf o u n d a t i o nf o rf m sd e s i g na n d r u n n i n g ，a n de s t a b l i s hab a s i sf o rf u l l yu t i l i z i n gf m sp e r f o r m a n c ei na c t u a lp r o d u c t i o n k e y w o r d s ：f l e x i b l em a n u f a c t u r i n gs y s t e m ( f m s ) ；t o o lf l o w ；d e a d l o c kd e t e c t i o n ；d e a d l o c k a v o i d a n c e ；d o u b l e l a y e rg e n e t i ca l g o r i t h m 第1 章緒論 第1 章緒論 1 1 研究背景 制造企業(yè)的競爭力與產(chǎn)品的供貨周期、質(zhì)量和售后服務(wù)水平密切相關(guān)。先進(jìn)的生 產(chǎn)管理是實(shí)現(xiàn)競爭力的一個(gè)重要手段。生產(chǎn)調(diào)度作為生產(chǎn)管理的核心內(nèi)容和關(guān)鍵技 術(shù)，其目標(biāo)是在企業(yè)車間有限的資源約束下，合理制訂工件在相關(guān)設(shè)備上的加工順序 和加工時(shí)間，以達(dá)到所選定的生產(chǎn)性能指標(biāo)最優(yōu)。由此可知，科學(xué)地制定生產(chǎn)調(diào)度方 案，對(duì)于提高產(chǎn)品交貨期滿足率，縮短產(chǎn)品供貨周期、控制車間的在制品庫存和提高 企業(yè)生產(chǎn)率起著至關(guān)重要的作用。 在傳統(tǒng)上，生產(chǎn)調(diào)度的研究需要以一些公認(rèn)的假設(shè)為前提，這些假設(shè)一般包括： 1 ) 確定的被調(diào)度的工件集合；2 ) 確定的工件的工時(shí)，并且在安排計(jì)劃時(shí)全部工件都 已就位；3 ) 用于加工工件的設(shè)備資源是可以連續(xù)工作的。這類調(diào)度問題歸于靜態(tài)調(diào)度 問趔1 1 。 與上述理想狀況不同，實(shí)際生產(chǎn)中的很多情況往往是隨機(jī)發(fā)生的，例如工件會(huì)隨 機(jī)到達(dá)，機(jī)床會(huì)隨機(jī)發(fā)生故障，刀具會(huì)隨機(jī)發(fā)生破損等，這些隨機(jī)事件產(chǎn)生的擾動(dòng)將 使得預(yù)先規(guī)劃好的靜態(tài)調(diào)度方案難以正常執(zhí)行。因此，合理的生產(chǎn)調(diào)度應(yīng)該能夠在加 工過程中根據(jù)狀態(tài)的實(shí)時(shí)變化，對(duì)生產(chǎn)活動(dòng)進(jìn)行動(dòng)態(tài)地、實(shí)時(shí)地和持續(xù)地進(jìn)行優(yōu)化控 制，從而保證系統(tǒng)在加工過程遇到故障和擾動(dòng)時(shí)，能夠根據(jù)系統(tǒng)監(jiān)控到的實(shí)時(shí)狀態(tài)自 主修改原定的加工順序，優(yōu)化調(diào)度系統(tǒng)的所有資源，使f m s 持續(xù)地、穩(wěn)定地運(yùn)行。在 研究中，這類問題通常被稱為動(dòng)態(tài)調(diào)度問題。 早在上世紀(jì)5 0 年代就出現(xiàn)了動(dòng)態(tài)調(diào)度的概念。1 9 5 7 年，j a c k s o n 【2 j 便明確區(qū)分了靜 態(tài)調(diào)度和動(dòng)態(tài)調(diào)度的概念。最初對(duì)此研究的學(xué)者主要采用了啟發(fā)式方法或仿真方法。 近年來，隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，推動(dòng)了人工智能、遺傳算法、神經(jīng)網(wǎng)絡(luò)和仿真 技術(shù)等新方法的產(chǎn)生和發(fā)展，為動(dòng)態(tài)調(diào)度的研究提供了新工具、開辟了新思路。與此 同時(shí)，也為生產(chǎn)調(diào)度的實(shí)用化奠定了基礎(chǔ)。由于生產(chǎn)發(fā)展的不斷需求，動(dòng)態(tài)調(diào)度當(dāng)前 已成為生產(chǎn)調(diào)度研究中的熱點(diǎn)之一。 按調(diào)度對(duì)象的不同，生產(chǎn)中的動(dòng)態(tài)調(diào)度分為工件流動(dòng)態(tài)調(diào)度和刀具流動(dòng)態(tài)調(diào)度兩 類。 工件流動(dòng)態(tài)調(diào)度的對(duì)象主要包括系統(tǒng)內(nèi)待加工或加工后的工件以及機(jī)床、工件運(yùn) 輸小車( a g v ) 、托盤和緩沖區(qū)等設(shè)備資源。動(dòng)態(tài)調(diào)度的內(nèi)容主要包括工件的加工順 序及設(shè)備資源的服務(wù)順序等【3 圳。這一類問題的研究較為深入而廣泛，采用的研究方法 主要有p e t d 網(wǎng)方法【5 - 9 j ，遺傳進(jìn)化算法【1 0 - 1 1 1 ，神經(jīng)網(wǎng)絡(luò)、法【1 2 1 3 1 ，基于知識(shí)的調(diào)度方法【1 4 1 6 】 哈爾濱- t 稃大學(xué)博十學(xué)位論文 以及其他一些啟發(fā)式調(diào)度方法【1 7 郴1 和自適應(yīng)算法【2 0 1 等等。 刀具流動(dòng)態(tài)調(diào)度主要包括刀具需求計(jì)劃和刀具實(shí)時(shí)分派兩方面內(nèi)容。刀具需求計(jì) 劃是指對(duì)于給定的一批加工工件，系統(tǒng)應(yīng)該配置多少類刀具，每類刀具應(yīng)配置多少把， 才能滿足工件加工的需要或者達(dá)到較高的生產(chǎn)率等問題。刀具實(shí)時(shí)分派是指在刀具流 不發(fā)生死鎖的前提下，如何在決策點(diǎn)為各加工機(jī)床分派刀具，才能得到較好的系統(tǒng)性 能，其中包括了刀具決策、刀具運(yùn)輸、刀具失效處理及刀具流死鎖檢測與避免等諸多 子問題。 在f m s 運(yùn)行中，刀具流和工件流同時(shí)存在并相互依附。工件流驅(qū)動(dòng)刀具流為之準(zhǔn) 備所需刀具，而有限的刀具資源又制約著工件流的各項(xiàng)決策和運(yùn)行過程，所以對(duì)刀具 流動(dòng)態(tài)調(diào)度的研究包括刀具實(shí)時(shí)分派的同時(shí)又不可避免地必須將工件的動(dòng)態(tài)排序包 括進(jìn)來。由于長期以來對(duì)工件流研究比較集中而忽略了對(duì)刀具流的研究，所以目前刀 具流的調(diào)度理論還比較薄弱，實(shí)際運(yùn)行中的刀具流自動(dòng)化水平也較低，相關(guān)文獻(xiàn)主要 集中在對(duì)刀具流靜態(tài)調(diào)度【2 1 銣1 的研究及不考慮工件流的刀具流動(dòng)態(tài)調(diào)度研究【3 1 確】，這 種現(xiàn)狀已經(jīng)在較大程度上影響了f m s 生產(chǎn)能力的進(jìn)一步發(fā)揮，因此，為了提高系統(tǒng)的 總體加工性能和充分發(fā)揮f m s 本身的柔性，進(jìn)一步深入研究刀具流的調(diào)度是十分必要 的。 1 2 刀具流動(dòng)態(tài)調(diào)度研究現(xiàn)狀綜述 1 2 1 刀具流的作用及其物理模型 ( 1 ) 刀具流的地位與作用 刀具作為生產(chǎn)制造系統(tǒng)的重要加工資源，對(duì)系統(tǒng)的生產(chǎn)率和利用率起著重要的作 用，同時(shí)刀具的購買成本比較大，約占系統(tǒng)總費(fèi)用的2 0 3 0 t 3 7 1 。另外由于生產(chǎn)加工 的需要，刀具頻繁的在各機(jī)床之間及機(jī)床與中央刀庫之間進(jìn)行交換和流動(dòng)，因此迫切 需要一個(gè)功能完善的刀具管理系統(tǒng)對(duì)刀具進(jìn)行管理和調(diào)度，以實(shí)現(xiàn)系統(tǒng)中刀具資源的 充分利用。 f m s 中的機(jī)床設(shè)備一般都配備有刀具庫，以存儲(chǔ)當(dāng)前加工所需的刀具并實(shí)現(xiàn)加工 過程中的快速換刀。每臺(tái)機(jī)床刀具庫的容量一般為3 0 - 6 0 把，有些大容量刀具庫可容 納刀具7 0 1 0 0 把【3 7 1 。f m s 在早期建立的加工范圍不大，機(jī)床刀具庫存儲(chǔ)的刀具基本 上都能滿足加工的需求，因此刀具的交換和流動(dòng)不大，系統(tǒng)對(duì)刀具的調(diào)度和信息管理 的要求不高。隨著社會(huì)對(duì)產(chǎn)品多樣化、低加工成本及短制造周期等需求日趨迫切，要 求現(xiàn)代的f m s 具有更高的柔性，能夠?qū)崿F(xiàn)多品種工件的加工。同時(shí)，為降低f m s 的生 產(chǎn)投入成本，機(jī)床刀具庫的容量也減少了，所以僅僅依靠有限的機(jī)床刀具庫所存儲(chǔ)的 刀具是不能夠滿足一臺(tái)機(jī)床加工的所有用刀需求的【3 3 1 ，故解決的辦法是增加中央刀庫 2 第1 章緒論 或者實(shí)現(xiàn)各機(jī)床刀庫之間刀具的高度共享，在這種情況下，f m s 中刀具流調(diào)度和控 制問題逐漸凸顯出來。 與已有的工件流調(diào)度控制理論相比較，現(xiàn)有的刀具流控制理論還很少很不成熟， 所導(dǎo)致的刀具管理技術(shù)水平的低下直接影響了f m s 的生產(chǎn)效率、生產(chǎn)質(zhì)量和柔性的進(jìn) 一步發(fā)揮【3 9 4 0 1 。g r a y ，s e i d m a n n 和s t e c k e 4 1 1 等人指出，刀具流調(diào)度理論的薄弱導(dǎo)致了 實(shí)際生產(chǎn)中f m s 運(yùn)行困難，阻礙了f m s 生產(chǎn)能力的進(jìn)一步發(fā)揮。c a r r i e 和p e r e r a 4 2 1 認(rèn)為， 有效的刀具管理可以提高系統(tǒng)的經(jīng)濟(jì)效益。s u r i 和w h i t n e y l 4 3 】則強(qiáng)調(diào)指出了刀具流調(diào)度 在f m s 的調(diào)度控制中占有十分重要的地位?？傊?，人們對(duì)刀具管理系統(tǒng)以及刀具調(diào)度 理論的研究在不斷的深入。由此可見，刀具流作為柔性制造系統(tǒng)的一個(gè)重要組成部分， 在f m s 的生產(chǎn)過程中占有十分重要的地位，它的管理是否完善，調(diào)度是否合理，控制 是否有效，對(duì)整個(gè)柔性制造系統(tǒng)的利用率、生產(chǎn)效率、生產(chǎn)質(zhì)量和加工成本都將產(chǎn)生 很大的影響郴】。 ( 2 ) 刀具流的物理模型 通過分析國內(nèi)外現(xiàn)有的f m s 刀具流系統(tǒng)【4 6 - 5 0 l ，可以發(fā)現(xiàn)它們的組成一般都包括： 1 ) 刀具管理計(jì)算機(jī)：計(jì)算機(jī)刀具調(diào)度系統(tǒng)軟件是刀具調(diào)度系統(tǒng)的大腦部分，負(fù) 責(zé)指揮、操作整個(gè)制造系統(tǒng)的刀具調(diào)度、運(yùn)送、刀具購買計(jì)劃等； 2 ) 刀具進(jìn)出站：人與刀具自動(dòng)輸送系統(tǒng)的連接點(diǎn)。設(shè)有多個(gè)存放刀具的刀位， 每個(gè)刀位都設(shè)有監(jiān)控開關(guān)。新刀由此進(jìn)入系統(tǒng)，磨損、破損的刀具由此輸出； 3 ) 刀具輸送網(wǎng)絡(luò)：主要采用自動(dòng)引導(dǎo)小車或刀具機(jī)械手等裝置完成正?；虍惓?，( 如磨損、破損) 刀具的輸送和更換； 4 ) 刀具存貯區(qū)：包括局部機(jī)床刀庫和中央刀庫。機(jī)床刀庫刀具容量有限，一般 存放3 0 6 0 把刀具，主要存儲(chǔ)本機(jī)床加工零件所需的全部或部分刀具，刀庫結(jié)構(gòu)多為鏈 式，容量較大而且容易擴(kuò)充。中央刀具庫的容量很大，可容納數(shù)千把各種刀具，主要 用于儲(chǔ)存機(jī)床加工零件的各種刀具，機(jī)床不急需使用的刀具，加工某工序所需的特殊 刀具及各種刀具的備用刀具等。 圖1 1 所示的刀具流物理模型概括了各類刀具流系統(tǒng)的總體結(jié)構(gòu)。在此模型中， f m s 由m 個(gè)柔性制造單元( f l e x i b l em a n u f a c t r u i n gc e l l ，f m c ) 構(gòu)成，每個(gè)f m c 由n 臺(tái)機(jī) 床組成。該模型的刀具流包括以下內(nèi)容： 預(yù)調(diào)好的刀具由刀具進(jìn)出站進(jìn)入系統(tǒng)，然后由刀具輸送裝置按刀具分派表將刀具 送至每個(gè)機(jī)床的局部機(jī)床刀庫。局部機(jī)床刀庫用來裝載目前加工所需的刀具，它的配 置是根據(jù)目前機(jī)床的加工零件、加工負(fù)荷實(shí)現(xiàn)的。機(jī)床按被加工工件的要求，可以直 接通過刀具輸送裝置從刀具進(jìn)出站、中央刀具庫或其它機(jī)床的局部機(jī)床刀庫調(diào)取所需 要的刀具。在實(shí)際加工過程中，機(jī)床可一邊加工，一邊往自己的刀具庫調(diào)用要求的刀 具。中央刀具庫是系統(tǒng)級(jí)刀具庫，主要用于貯存系統(tǒng)中加工工件所需的各種刀具及備用 哈爾濱t 程大學(xué)博十學(xué)位論文 刀具。任何破損、磨損的刀具從機(jī)床刀庫返回到中央刀庫，進(jìn)行修繕之后繼續(xù)投入系 統(tǒng)使用。將中央刀具庫通過刀具自動(dòng)輸送裝置與刀具進(jìn)出站及各局部機(jī)床刀具庫連接 起來，就可形成自動(dòng)刀具供給系統(tǒng)。 圖1 1 刀具流物理模型 f i g i 1p h y s i c a lm o d e lo ft o o lf l o w 1 2 2 刀具流調(diào)度建模方法研究綜述 與工件流研究相比較，刀具流的研究時(shí)間還很短，相關(guān)文獻(xiàn)主要集中在介紹刀具 管理系統(tǒng)的功能、體系結(jié)構(gòu)及狀態(tài)監(jiān)控 5 1 - 5 7 】，而與實(shí)際加工過程相關(guān)的刀具調(diào)度理論 研究1 3 8 , 5 8 5 9 貝1 j 不多見，這主要是由于f m s 趨向于小批量復(fù)雜零件的生產(chǎn)，刀具的需求 數(shù)量和種類非常大，刀具流的控制和決策相當(dāng)復(fù)雜，故對(duì)該領(lǐng)域的研究具有一定的難 度。因此。對(duì)刀具流進(jìn)行更深入的研究具有重要的理論意義和工程實(shí)用價(jià)值。 刀具流的研究首先應(yīng)從建模開始，只有針對(duì)紛繁復(fù)雜的刀具系統(tǒng)做高度的抽象， 提取其本質(zhì)要素，忽略其次要因素，構(gòu)建出合理的模型，才能夠更好地開展進(jìn)一步調(diào) 度研究。常用的建模方法主要可分為以下三類： ( 1 ) 基于p e t r i 網(wǎng)的建模方法 為了全面形式化的描述柔性制造系統(tǒng)的運(yùn)行狀態(tài)，許多研究人員都采用p e t r i 網(wǎng) 為f m s 建模。c r e d d y t 6 0 】采用時(shí)間p e t r i 網(wǎng)對(duì)中心刀具管理系統(tǒng)進(jìn)行建模，并研究了 刀具預(yù)定時(shí)間和刀具數(shù)目對(duì)系統(tǒng)完工時(shí)間的影響，但其研究是在分級(jí)控制模式的假設(shè) 下進(jìn)行的，且刀具不能在機(jī)床間共享，限制了系統(tǒng)的靈活性；k b a r k a o u i 6 l 】采用 隨機(jī)p e t r i 網(wǎng)進(jìn)行建模，在此基礎(chǔ)上對(duì)機(jī)床的利用率及刀具運(yùn)輸時(shí)間進(jìn)行了仿真評(píng)估。 但其刀具共享策略是整批刀具更換，增加了刀具資金投入的同時(shí)也限制了機(jī)床共享刀 4 第1 章緒論 具的靈活性。f f c h e n 【6 3 】針對(duì)動(dòng)態(tài)刀具分派下的多級(jí)多機(jī)柔性制造系統(tǒng)，采用面向?qū)?象的著色p e t r i 網(wǎng)進(jìn)行建模，大大降低了系統(tǒng)的復(fù)雜性。并對(duì)不同刀具需求選擇規(guī)則 下的系統(tǒng)性能進(jìn)行了評(píng)估。畢諸明等【6 2 】為預(yù)測被i 9 1 j j f m s 運(yùn)控軟件中刀具流引起的死鎖 和回避功能。首先建立了刀具流的p n 模型，然后從網(wǎng)模型中變遷的等待關(guān)系來定義f m s 刀具流的死鎖現(xiàn)象，但是該模型只局限于刀具流內(nèi)部，沒有考慮工件流對(duì)刀具流的影 響。舒海生等【叫運(yùn)用面向?qū)ο蠹夹g(shù)和高級(jí)p e t r i 網(wǎng)，針對(duì)工序備刀情況為柔性制造系 統(tǒng)建立了一個(gè)含機(jī)床故障處理的動(dòng)態(tài)調(diào)度仿真模型，該模型層次分明，故障處理流程 十分簡潔，較好地反映了系統(tǒng)的運(yùn)行情況，但模型中未包含刀具失效的處理。 可見，p e t r i 網(wǎng)作為一種形式化的建模方法可以很好的描述柔性制造系統(tǒng)中可能 發(fā)生的各種變化以及變化間的關(guān)系。然而，隨著制造系統(tǒng)中工件和資源的數(shù)量、種類 的增加，采用p e t r i 網(wǎng)方法進(jìn)行分析將引起系統(tǒng)控制模型的復(fù)雜化，不利于構(gòu)建高效 的實(shí)時(shí)控制算法。 ( 2 ) 基于圖論的建模方法 為了描述柔性制造系統(tǒng)中工件和資源的交互關(guān)系，一些研究人員采用了圖論方法 為f m s 建模。h o u s n id j e l l a b t 6 5 】針對(duì)工件加工順序和刀具的載入順序問題，采用超圖法 進(jìn)行描述，并用啟發(fā)式算法求解，目標(biāo)是最小化換刀次數(shù)。g e b r a e e l t 6 6 】針對(duì)刀具共 享策略利用圖論方法建立了刀具資源分派圖，圖中頂點(diǎn)集合分別與工件資源和刀具資 源相對(duì)應(yīng)，邊的集合表示了工件對(duì)刀具資源的需求和刀具資源對(duì)工件的分派，權(quán)集表 示了工件對(duì)刀具的占有和釋放順序，該圖用簡潔精確的方式描繪了系統(tǒng)中刀具的分派 和需求，但該模型的描述只局限于刀具流內(nèi)部。l e ecs t 6 7 】針對(duì)f m s 中工件加工順序 和刀具選擇問題，對(duì)每個(gè)工件的多個(gè)可行的操作順序建立了網(wǎng)絡(luò)結(jié)構(gòu)圖，圖中每個(gè)節(jié) 點(diǎn)包含著一個(gè)操作號(hào)及其加工所需的刀具和加工時(shí)間等信息，弧代表兩個(gè)操作之間的 先后關(guān)系，然后以最小化等刀時(shí)間為目標(biāo)，通過左移和右移操作選擇一個(gè)可行的操作 順序。 圖論方法簡單直觀，可以清晰地反映系統(tǒng)中工件和資源在當(dāng)前狀態(tài)下的交互狀態(tài) 信息，但是該方法不適合于系統(tǒng)的動(dòng)態(tài)行為描述。 ( 3 ) 基于整數(shù)規(guī)劃的建模方法 一些研究者基于運(yùn)籌學(xué)原理，采用整數(shù)規(guī)劃的方法為系統(tǒng)建模。t s a t a n 6 8 j 對(duì) 機(jī)器分派和刀具分配問題，以最小化刀具配置數(shù)量和最大化刀具利用率為目標(biāo)，以刀 具存儲(chǔ)區(qū)容量為約束條件，采用整數(shù)規(guī)劃方法進(jìn)行建模。a t m a n i a 【6 9 】針對(duì)f m s q 丁的機(jī) 器刀具分配和操作分派問題，以最小化總的成本為目標(biāo)，以刀具庫容量和刀具壽命為 約束條件，建立了混合整數(shù)線性規(guī)劃模型，且一個(gè)操作可以在不同的機(jī)床上加工，即考 慮了可替代機(jī)床情況；g a m i l ama t 7 0 】針對(duì)工件刀具的載入和調(diào)度問題，以機(jī)床刀具庫 容量和刀具壽命為約束條件，建立混合整數(shù)線性規(guī)劃模型進(jìn)行工件刀具的初始分派， 哈爾濱t 程大學(xué)博十學(xué)何論文 然后根據(jù)模型的輸出結(jié)果進(jìn)行工件的調(diào)度。s gp o n n 鋤b a l 眥【7 1 】和r a h u ls w a r n k a r 【7 2 】 針對(duì)f m s 中的機(jī)床選擇、工序分派和刀具需求問題，以最小化系統(tǒng)的不平衡度和最大化 系統(tǒng)的輸出為目標(biāo)建立了數(shù)學(xué)模型。s b i l g i n 7 3 1 針對(duì)f m s 中的操作運(yùn)行分解的情況下 的調(diào)度分派問題，以加工操作總的全重為目標(biāo)，以機(jī)床加工能力、刀具庫容量和刀具 拷貝數(shù)量為約束條件，建立混合整數(shù)規(guī)劃模型。 可見，利用整數(shù)規(guī)劃對(duì)系統(tǒng)建?？梢苑治鱿到y(tǒng)的生產(chǎn)率、平均流通時(shí)間等性能指 標(biāo)，但它很難將車間的其它資源( 如：a g v 、刀具機(jī)械手等) 考慮進(jìn)去，并且很難處 理系統(tǒng)出現(xiàn)異常時(shí)的情況。 綜上所述，現(xiàn)有刀具流的建模一方面大多局限在刀具流內(nèi)部，而工件流對(duì)刀具流 的影響則考慮得較少；另一方面基本上只考慮了系統(tǒng)處于正常狀態(tài)下刀具流的流動(dòng)， 沒有包含對(duì)故障( 刀具失效等) 的處理。事實(shí)上，在f m s 運(yùn)行中，工件流和刀具流是 同時(shí)存在并相互影響的，在刀具流建模過程中應(yīng)該考慮到與工件流進(jìn)程之間的相互作 用，而刀具失效等異常情況在系統(tǒng)運(yùn)行中也是時(shí)有發(fā)生的，因而在建模時(shí)也應(yīng)予以考 慮。此外，現(xiàn)有刀具流( 包括工件流) 的研究大多將工序加工不可中斷這一前提作為 建模的出發(fā)點(diǎn)，而事實(shí)上在實(shí)際加工過程中，尤其是在高度自動(dòng)化的加工中心上，采 用的是工序集中原則，各工序往往包括了很多的工步，加工時(shí)間很長，因此，如果仍 然將工序不可中斷作為建模和調(diào)度的前提將會(huì)對(duì)刀具的利用率造成不利影響，而如果 將工序可中斷( 即以工步為備刀對(duì)象) 作為出發(fā)點(diǎn)，應(yīng)當(dāng)可以取得更好的效果，這一 方面的研究目前還很匱乏。 1 2 3 刀具流動(dòng)態(tài)調(diào)度方法研究綜述 在對(duì)考慮刀具流的制造系統(tǒng)建立模型后，就要構(gòu)造相應(yīng)的調(diào)度算法進(jìn)行問題求 解。刀具流動(dòng)態(tài)調(diào)度的一般研究方法可以分為兩大類：“仿真+ 規(guī)則 啟發(fā)式調(diào)度 和最優(yōu)化調(diào)度，其中最優(yōu)化調(diào)度又包括傳統(tǒng)優(yōu)化調(diào)度和智能優(yōu)化調(diào)度兩種。 ( 1 ) “仿真+ 規(guī)則 啟發(fā)式調(diào)度方法 由于f m s 加工的工件種類繁多，系統(tǒng)運(yùn)行時(shí)需要的刀具種類和數(shù)量是很多的，而 且這些刀具頻繁地在各機(jī)床之間、機(jī)床和刀庫之間進(jìn)行自動(dòng)交換。另外，刀具磨損和 各種偶然因素引起的刀具早期失效所造成的強(qiáng)制性或適應(yīng)性換刀，使得刀具流的規(guī)劃 和調(diào)度變得異常復(fù)雜，常規(guī)的規(guī)劃和調(diào)度方法是難以勝任的，不能充分地發(fā)揮f m s 的 生產(chǎn)效率和高柔性等生產(chǎn)潛力，因此人們往往采用“仿真+ 規(guī)則”的方法來解決這一問 題。 c h a n g y o n g 7 4 】分析了f m s 中工件的載入和刀具分派問題，以減少機(jī)床間刀具交換 次數(shù)為目標(biāo)建立一種啟發(fā)式調(diào)度算法，同時(shí)在調(diào)度過程中考慮了可替代刀具情況。 a r u ns k a s h y a p 7 5 】討論了f m s 中，在不同的刀具配置下刀具選擇規(guī)則和刀具分派規(guī)則 6 第1 章緒論 對(duì)系統(tǒng)完工時(shí)間和刀具機(jī)械手利用率的影響。h k r o h 7 6 j 針對(duì)機(jī)器載入、刀具分派和 工件加工順序問題，以最小化拖延期為目標(biāo)，提出三個(gè)啟發(fā)式算法。c h o o n gs o ol e e 【| 7 7 】 針對(duì)f m s 中的動(dòng)態(tài)刀具分派策略，提出了考慮刀具流調(diào)度的工件分派模型，該模型包 括兩部分，即工件選機(jī)床模型和機(jī)床選工件模型。目標(biāo)是最大化系統(tǒng)生產(chǎn)率及最小化 拖延工件的數(shù)量。h o u s n id j e l l a b t 6 5 1 針對(duì)工件加工順序和刀具的載入順序問題，采用超 圖法進(jìn)行描述，目標(biāo)是最小化換刀次數(shù)，并用啟發(fā)式算法求解。yf a t h i 7 8 】針對(duì)并行加 工環(huán)境中工件和刀具的調(diào)度問題提出三個(gè)啟發(fā)式算法，并以系統(tǒng)完工時(shí)間為目標(biāo)對(duì)三 種算法進(jìn)行了仿真分析。 k w a s i a g 7 9 j 討論了f v l s 中刀具共享情況下的刀具分派問題，針對(duì)三種不同的刀具 分派策略，提出相應(yīng)的啟發(fā)式算法，通過仿真考查它們對(duì)交貨期、拖延工件百分比和 工件平均流通時(shí)間的影響，但是沒有包含訂單到達(dá)、機(jī)床刀具故障等緊急情況的處理。 o z b a y r a km f 8 0 】針對(duì)f m s 中工件流和刀具流的調(diào)度問題進(jìn)行仿真研究，并對(duì)4 種刀具載 入策略和4 種工件調(diào)度規(guī)則組合下系統(tǒng)的性能指標(biāo)進(jìn)行了分析，但是沒有考慮可替代 工藝路線、可替代機(jī)床和可替代刀具情況。b u y u r g a nn 【8 l 】針對(duì)f m s 中存在可替代 刀具情況下的刀具選擇問題提出一種啟發(fā)式算法，所提的算法以刀具尺寸和刀具壽命 的比率l s 為依據(jù)進(jìn)行刀具選擇和分派，實(shí)例證明了算法的有效性，但是對(duì)刀具失效 等動(dòng)態(tài)情況沒有考慮。 s u r e s hk n 【8 2