第1章 緒論 

1.1  課題研究背景 
計算機技術(shù)的快速發(fā)展給其他領(lǐng)域的研究帶來了技術(shù)革新，各行各業(yè)紛紛將計算機技術(shù)應(yīng)用到實際研究中，如生產(chǎn)制造業(yè)，已從傳統(tǒng)的機械制造，轉(zhuǎn)向現(xiàn)代化生產(chǎn)管理，從制造到生產(chǎn)，以及整個過程的管理均采用現(xiàn)代計算機技術(shù)進(jìn)行了技術(shù)革新。其中，備受學(xué)者關(guān)注的生產(chǎn)調(diào)度也成為技術(shù)革新的重要環(huán)節(jié)，多年來調(diào)度管理早已與現(xiàn)代計算機技術(shù)、數(shù)據(jù)管理技術(shù)相結(jié)合。如何提高生產(chǎn)效率成為主要研究課題。 生產(chǎn)效率關(guān)系著產(chǎn)品完工時間、產(chǎn)品完工質(zhì)量，對現(xiàn)代制造業(yè)有實際的研究意義。調(diào)度研究已經(jīng)成為一個發(fā)展久遠(yuǎn)的研究體系，調(diào)度也隨著技術(shù)革新，隨之賦予新的含義：根據(jù)調(diào)度環(huán)境特點，結(jié)合現(xiàn)代計算機技術(shù)合理安排調(diào)度策略，達(dá)到盡早完工、提高制造效率、降低設(shè)備損耗、節(jié)約制造材料、節(jié)約能源、減輕運輸壓力等目標(biāo)，這個生產(chǎn)制造過程稱之為完整的調(diào)度過程。 調(diào)度問題由于其發(fā)展的特殊性，也成為著名的 NP-hard 問題，備受各界學(xué)者的廣泛關(guān)注。早期的調(diào)度研究被提出后，各種優(yōu)化方法紛紛涌現(xiàn)，成果豐富，為機械制造過程、海陸運輸、物資調(diào)度、通信傳輸?shù)葞砹诉M(jìn)步。近代，隨著大數(shù)據(jù)時代的到來，調(diào)度研究不局限于機械制造，調(diào)度過程也不局限于工業(yè)問題，所以調(diào)度環(huán)境、調(diào)度目的成為實際生產(chǎn)調(diào)度的前提，這種復(fù)雜的調(diào)度過程具有實際的研究意義。 細(xì)數(shù)傳統(tǒng)優(yōu)化方案，著名的調(diào)度算法有：免疫調(diào)度算法[1]、遺傳算法[2]和微分進(jìn)化法[3]等，再如針對小批量復(fù)雜化產(chǎn)品的免疫進(jìn)化算法[4,5]、蟻族優(yōu)化算法[6]、粒子群算法[7,8]、基于神經(jīng)網(wǎng)絡(luò)的作業(yè)車間調(diào)度算法[9]，此外，還有解決設(shè)備固定瓶頸的靜態(tài)調(diào)度算法[10]，通過隨機序列策略解決柔性調(diào)度的算法[11,12]，啟發(fā)式算法與動態(tài)組合優(yōu)化的混合算法研究[13]，還有結(jié)合離散數(shù)學(xué)建立解決數(shù)控機床的調(diào)度算法[14]等。
........

1.2  國內(nèi)外研究現(xiàn)狀及分析 
國內(nèi)外調(diào)度問題的研究由來已久，從傳統(tǒng)的手工制造、機械制造，到現(xiàn)代應(yīng)用計算機技術(shù)的調(diào)度研究，最初學(xué)者們明確了生產(chǎn)中的兩個方向性問題：加工問題和組合問題。加工過程考慮工件加工之間的關(guān)系，如何排序成為復(fù)雜的多項式組合問題；而組合問題，在生產(chǎn)中體現(xiàn)在裝配、運輸、調(diào)配物資等方面，如何組合成為運籌學(xué)的研究課題[22]。 很多經(jīng)典的調(diào)度優(yōu)化算法研究加工問題，如圖 1-1 所示，考慮工序之間的加工關(guān)系；而研究組合問題，如圖 1-2 所示，考慮工序生產(chǎn)過程的組合裝配問題，這需要將產(chǎn)品加工細(xì)化為很多工件的加工，工件之間需要進(jìn)行裝配或運輸處理，針對這個部分做組合優(yōu)化研究[23]。但有些學(xué)者發(fā)現(xiàn)，將兩個關(guān)聯(lián)性很強的部分獨立研究，造成了研究的瓶頸，研究結(jié)果也與實際狀況有所差距，所以綜合調(diào)度算法應(yīng)運而生[24]。隨著實際生產(chǎn)環(huán)境的復(fù)雜變化，綜合調(diào)度著眼于分布式調(diào)度問題，并結(jié)合實際生產(chǎn)面臨的多車間、工序遷移、特殊工序等問題展開研究，并得到了一定的研究成果[25,26]。  
..........

第2章 綜合調(diào)度問題綜述 

2.1  綜合調(diào)度問題背景 

以往制造生產(chǎn)優(yōu)化研究往往將加工與裝配問題分為兩個課題進(jìn)行研究，隨之而產(chǎn)生的問題對實際生產(chǎn)造成的影響不可忽視：加工與裝配關(guān)系緊密，分開研究割裂加工與裝配的約束關(guān)系造成結(jié)果失真。當(dāng)大批量流水線生產(chǎn)滿足不了社會要求后，小批量復(fù)雜產(chǎn)品的生產(chǎn)成為了主流，而加工與裝配分開研究成為了主要瓶頸，而綜合調(diào)度解決了這一問題。統(tǒng)一加工與裝配定義為工序，并用工藝樹表示工序之間的縱向和橫向關(guān)系，模擬了實際生產(chǎn)的加工狀態(tài)，更進(jìn)一步的，根據(jù)加工環(huán)境的不同，設(shè)定相應(yīng)的約束條件，如緊密銜接工序、零等待工序、柔性加工工序等特殊問題，提出了解決特殊加工的綜合調(diào)度算法。

........

2.2  問題模型概述 
綜合調(diào)度統(tǒng)一工序加工與工序裝配，為了合理的表示工序之間的關(guān)系，應(yīng)用工藝樹模擬表示產(chǎn)品加工關(guān)系，縱向表示工件之間的關(guān)系，橫向表示工序之間的序列關(guān)系。如圖 2-1 工藝樹，橫向關(guān)系如 A4、A3 表示工序加工次序與靜態(tài)加工時間關(guān)系。縱向關(guān)系如 A5、A6 表示工件之間關(guān)聯(lián)性，工藝樹的標(biāo)準(zhǔn)表示法，一般為 An/Mn/Tn，簡略表示為 A6/2/15。擬關(guān)鍵路徑法從靜態(tài)角度考慮影響加工完工時間的因素，但加工是動態(tài)過程，靜態(tài)工藝樹能反應(yīng)工序之間的靜態(tài)關(guān)系，所以綜合調(diào)度算法進(jìn)一步提出動態(tài)關(guān)鍵路調(diào)度算法，隨加工過程的動態(tài)進(jìn)行，更新關(guān)鍵路徑，動態(tài)掌握影響加工進(jìn)程的長路徑工序，根據(jù)動態(tài)路徑調(diào)整加工次序，得到最優(yōu)調(diào)度結(jié)果，大大縮短工期，合理調(diào)整工序加工次序[36]。多數(shù)調(diào)度算法考慮工序之間的關(guān)系，而設(shè)備的高效利用也是盡早完工的關(guān)鍵，所以設(shè)備空閑驅(qū)動策略解析了設(shè)備空閑和設(shè)備忙兩種狀態(tài)，設(shè)備驅(qū)動需以空閑為信號，若可加工工序不唯一，按照長路徑短用時進(jìn)行排序，達(dá)到空閑時間利用高效，并盡早完工的目標(biāo)。設(shè)備忙狀態(tài)，提高設(shè)備并行機制，縱向提高設(shè)備利用率。 
............

第 3 章  利用工序遷移時間的兩車間設(shè)備驅(qū)動綜合調(diào)度算法 ............ 10 
3.1  引言 ..... 10 
3.2  問題模型描述 ....... 11 
3.3  問題分析與相關(guān)概念 .... 11
3.4  策略設(shè)計 ...... 12
3.5  調(diào)度算法設(shè)計 ....... 14 
3.6  實例分析與對比 ............ 16 
3.7  本章小結(jié) ...... 24 
第 4 章  利用工序遷移時間的三車間綜合調(diào)度算法 .......... 25 
4.1  引言 ..... 25
4.2  三車間調(diào)度的數(shù)學(xué)模型 ......... 26 
4.3  問題分析 ...... 26 
4.3.1  三車間設(shè)備分析 ..... 26
4.3.2  三車間遷移問題分析 ...... 27 
4.4  策略設(shè)計 ...... 28
4.5  調(diào)度算法設(shè)計 ....... 31
4.6  算法對比分析 ....... 33 
4.7  本章小結(jié) ...... 37 
第 5 章 利用工序遷移時間的多車間綜合調(diào)度算法 .......... 39 
5.1  引言 ..... 39 
5.2  多車間非對稱資源加工模型 .......... 40 
5.3  問題分析 ...... 41
5.4  策略設(shè)計 ...... 42 

第5章    利用工序遷移時間的多車間綜合調(diào)度算法

5.1  引言 
傳統(tǒng)的調(diào)度方法將加工與裝配問題分開解決，但隨著研究的深入，綜合調(diào)度算法提出將加工與裝配統(tǒng)一定義為工序，明確了加工不是單一處理的過程，，裝配也不是獨立的環(huán)節(jié)，所以兩者協(xié)同作用可以解決適用范圍廣一般綜合調(diào)度問題、對應(yīng)特殊環(huán)境的特殊調(diào)度問題。隨著工業(yè)的進(jìn)步，兩車間、多車間調(diào)度成為企業(yè)提高生產(chǎn)效率的手段，但隨之而來的工序遷移問題成為了學(xué)者研究的方向。 為了解決多車間復(fù)雜環(huán)境下的加工問題，并達(dá)到盡早完工的目的，首先考慮了設(shè)備利用率高的設(shè)備空閑驅(qū)動策略，思路是：設(shè)備空閑驅(qū)動策略是以設(shè)備空閑為驅(qū)動信號，只要設(shè)備空閑就去調(diào)度可加工工序；而在多車間加工環(huán)境下，會出現(xiàn)相同設(shè)備均空閑(不唯一)的情況，處理過程設(shè)計為：1．判斷可加工工序，若其緊前工序所在車間設(shè)備也空閑，為減少遷移次數(shù)則安排在緊前工序所在車間；2．若可加工工序判斷出工序必發(fā)生遷移，則任意安排工序加工車間。3．若某空閑設(shè)備可加工的工序不止一個，可加工工序均按條件競爭設(shè)備，其中選擇長路徑上用時短的工序效果更優(yōu)。 但通過綜合研究分析表明：對于多車間復(fù)雜加工環(huán)境下的調(diào)度問題，工序在車間之間的遷移已經(jīng)成為一個不可避免的問題，若僅僅從減少遷移次數(shù)上研究，不考慮遷移時間，更不考慮如何利用遷移時間，那么設(shè)備空閑驅(qū)動策略需進(jìn)一步完善。所以，為了考慮工序如何合理選擇加工車間，考慮復(fù)雜多變的遷移時間如何利用，本章提出了利用工序遷移時間的多車間綜合調(diào)度算法。
.........

結(jié)論 

本文的算法以兩車間、三車間、多車間為研究環(huán)境，研究工序在不單一車間之間的調(diào)度，重點在于設(shè)備分布多樣化的情況下如何遷移工序，算法研究具有實際意義，綜合總結(jié)本文如下： 
1．從工序遷移問題出發(fā)，考慮工序遷移時間、工序遷移策略，做到合理遷移并利用遷移時間的目的。為了有效減少兩車間設(shè)備空閑等待時間，提出兩車間設(shè)備空閑驅(qū)動策略，每當(dāng)設(shè)備空閑即對可加工工序進(jìn)行尋找，并采用長路徑和短用時策略排序，調(diào)度設(shè)備每個空閑時刻搜索到的可加工工序；提高設(shè)備利用率，減少遷移時間占用設(shè)備加工時間，提出遷移時間利用策略，使設(shè)備工作效率提高。實例表明，該算法可充分利用設(shè)備空閑時間提高設(shè)備利用率。
2．為了對兩車間調(diào)度問題進(jìn)行擴展，研究了三車間設(shè)備各種組合分布情況，在不同的情況下分析影響工序調(diào)度的因素，在早加工結(jié)束并合理遷移的目標(biāo)下研究調(diào)度算法。首先，為了解決三車間復(fù)雜環(huán)境下車間選擇問題，分析各個工序與其緊前、緊后工序設(shè)備之間的關(guān)系，根據(jù)設(shè)備之間的關(guān)聯(lián)性，合理安排工序加工車間。其次，以往加工過程中，設(shè)備空閑才開始調(diào)度工序，若遇到遷移情況，設(shè)備需等待遷移工序，造成了遷移延誤時間，為了降低遷移延誤時間，提出待加工工序預(yù)判斷策略，在緊前工序完工時間，釋放的待加工工序中進(jìn)行預(yù)判斷，若需發(fā)生遷移，則提前遷移到所需車間。最后，有些遷移無法預(yù)先完成，造成了設(shè)備等待遷移的延誤時間，為了利用遷移等待時間，提出遷移時間利用策略，在無法預(yù)遷移而造成的遷移等待時間內(nèi)安排閑置工序加工，使設(shè)備有效利用遷移時間。
3．最后一章算法繼承前兩章的算法研究成果，擴展到多車間調(diào)度研究。針對多車間工序遷移問題，為了解決遷移時間影響產(chǎn)品加工時間的綜合調(diào)度問題，提出了利用工序遷移時間的多車間綜合調(diào)度算法。為了解決多車間復(fù)雜環(huán)境下車間選擇問題，提出多車間設(shè)備屬性車間選擇策略，根據(jù)工序設(shè)備屬性與緊前、緊后工序加工設(shè)備的關(guān)聯(lián)性合理安排工序加工車間；為了降低遷移延誤時間，提出待加工工序預(yù)判斷策略，在工序釋放時刻安排遷移工序預(yù)遷移到加工車間；為了利用遷移等待時間，提出遷移時間利用策略，在無法預(yù)遷移而造成的遷移等待時間內(nèi)安排閑置工序加工，使設(shè)備有效利用遷移時間。實例表明，該算法可充分利用設(shè)備空閑時間提高設(shè)備利用率，并有效利用遷移時間達(dá)到盡早完工的目的，且算法復(fù)雜度不高于二次多項式。 
.........
參考文獻(xiàn)(略)

本文編號：84420