柔性開放車間調(diào)度算法研究.pdf

1、在制造領域,調(diào)度是生產(chǎn)管理的核心和關鍵技術,合理的調(diào)度可以縮短制造期、減少資源浪費,提高經(jīng)濟效益。隨著生產(chǎn)過程的日益復雜和競爭的加劇,調(diào)度的作用越來越重要。
　　 柔性開放車間調(diào)度問題(FOSSP)是生產(chǎn)中常見的調(diào)度問題,也是亟待解決的高難度組合優(yōu)化問題。本文主要研究加工可中斷、不可中斷和具有機器使用限制三種情況下的柔性開放車間調(diào)度問題(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN.1|Cm

2、ax)的數(shù)學建模和近似調(diào)度算法設計。針對問題特點,分別采用網(wǎng)絡流和半匹配理淪設計了相應的近似調(diào)度算法,并給出了算法的最壞情況界等性能參數(shù)。
　　 本文主要研究內(nèi)容包括以下五個方面:
　　 1.研究了柔性開放車間調(diào)度問題的數(shù)學建模方法。分析了可中斷、不可中斷和具有機器使用限制三種情況下柔性開放車間生產(chǎn)過程的約束條件,將它們形式化的表示為一組約束函數(shù),以制造期最短為優(yōu)化目標,建立了上述三種柔性開放車間調(diào)度問題的混合整數(shù)規(guī)劃模

3、型,為算法驗證奠定了基礎。
　　 2.以制造期最短為優(yōu)化目標,給出了基于網(wǎng)絡流的Om(P)|pmtn,ri|Cmax問題調(diào)度算法。算法將Om(P)|pmtn,ri|Cmax題分解為資源分配和工件排序兩個子問題,首先將調(diào)度問題轉(zhuǎn)化為網(wǎng)絡流模型,通過最大流算法確定使機器滿負荷工作的資源分配方案。為了提高最大流算法的效率,研究了融入加工領域知識的活躍頂點選擇策略,采用最小負載優(yōu)先和最大工作量優(yōu)先啟發(fā)式規(guī)則設計了高效率的最大流算法。針對

4、最大流存在陷入局部優(yōu)化的情況,給出了優(yōu)化方法。在最大流的基礎上,通過加工時間矩陣的減量集合確定工件的加工順序。
　　 3.針對Om(P)||Cmax問題求解難度大的特點,給出了以稠密調(diào)度為目標的近似調(diào)度算法求解方案,該方案將調(diào)度問題分解為資源匹配和調(diào)度優(yōu)化兩個子問題,每次資源匹配所有工件都僅完成一個操作,那么具有m個操作的工件集合需要進行m次資源匹配,通過連接各資源匹配結(jié)果得到初步調(diào)度解,最后對初步調(diào)度解進行優(yōu)化,消除不必要的機

5、器空閑時間,得到稠密調(diào)度解。在兩個子問題中,資源匹配是核心問題,文中采用賦權二分圖進行建模,通過半匹配求得負載差異最小的資源匹配結(jié)果,并且針對小規(guī)模和大規(guī)模問題分別設計了基于最優(yōu)增廣路徑和基于遺傳算法的最優(yōu)半匹配算法。在資源匹配的基礎上,本文給出了初步調(diào)度解的構造方法及其優(yōu)化方法。
　　 4.研究了Om(P)|r,αN,1|Cmax問題制造期下界的計算方法。由于存在機器使用限制,無法通過簡單的方法獲得制造期的下界。因此,本文通過

6、約束松弛將原問題轉(zhuǎn)化為機器使用限制下可中斷柔性開放車間調(diào)度問題(Om(P)|r,αN.1,pmtn|Cmax),Om(P)|r,αN.1,pmtn|Cmax易于解決,將它的最短制造期作為Om(P)|r,αN.1|Cmax問題制造期的下界。具體的解決方法是首先建立Om(P)|r,αN.1,pmtn|Cmax問題的混合整數(shù)規(guī)劃模型,在此基礎上將模型中的約束條件轉(zhuǎn)化為弧的容量約束,得到問題的網(wǎng)絡流模型。然后,通過最大流算法求得它的制造期,以此

7、作為Om(P)|r,αN.1|Cmax問題的制造期下界。
　　 5.針對Om(P)|r,αN.1|Cmax問題,給出了最壞情況界為2的稠密調(diào)度算法。Om(P)|r,αN.1|Cmax問題允許機器在制造期內(nèi)含有一個不可用時間窗,并且被中斷工件在機器恢復可用后可以繼續(xù)加工。文中將機器的不可用時間窗定義為虛擬工件,它的加工起止時間等于不可用時間窗的開始時間和結(jié)束時間。為了降低問題的難度,首先在不考慮虛擬工件的情況下進行資源匹配,進而通

8、過分析虛擬工件與資源匹配制造期間的關系,得到三種模式關系。針對每種模式的特點,給出了考慮虛擬工件后的資源匹配調(diào)整方法。在此基礎上,設汁了Om(P)|r,αN.1|Cmax問題的稠密調(diào)度算法。
　　 在算法性能研究方面,本文從理論和算例試驗兩個方面分析了上述三種柔性開放車間調(diào)度算法的性能。在理論上,分析了調(diào)度算法的時間復雜度和最壞情況界,并通過隨機產(chǎn)生的算例驗證了算法的正確性,結(jié)果表明算法能夠求得調(diào)度問題的有效解,并且制造期滿足最