第1章 緒論 

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

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

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

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

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

........

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

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

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

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

結(jié)論 

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

本文編號(hào)：84420