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

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

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

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

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

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

6、約束松弛將原問題轉(zhuǎn)化為機(jī)器使用限制下可中斷柔性開放車間調(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ī)劃模型,在此基礎(chǔ)上將模型中的約束條件轉(zhuǎn)化為弧的容量約束,得到問題的網(wǎng)絡(luò)流模型。然后,通過最大流算法求得它的制造期,以此

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

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