具有分段惡化效應(yīng)生產(chǎn)過(guò)程的智能優(yōu)化調(diào)度研究.pdf

1、調(diào)度問(wèn)題旨在將有限的資源分配給各項(xiàng)不同的任務(wù)，同時(shí)滿足特定的需求和約束，其廣泛存在于各類生產(chǎn)制造系統(tǒng)中。生產(chǎn)調(diào)度是制造系統(tǒng)中關(guān)鍵的決策過(guò)程之一，對(duì)其進(jìn)行優(yōu)化是車間管理的主要研究?jī)?nèi)容。采用合理的調(diào)度方案安排生產(chǎn)是提高制造系統(tǒng)作業(yè)效率的有效手段。在傳統(tǒng)的生產(chǎn)調(diào)度問(wèn)題中，通常認(rèn)為工件的加工時(shí)間固定不變。然而在某些實(shí)際制造和服務(wù)過(guò)程中，工件的加工時(shí)間會(huì)因其開(kāi)工時(shí)刻、加工位置的不同而發(fā)生變化，與傳統(tǒng)調(diào)度問(wèn)題相比生產(chǎn)過(guò)程具有惡化效應(yīng)，由此產(chǎn)生了一類

2、新的調(diào)度問(wèn)題。該類問(wèn)題中工件的加工時(shí)間由開(kāi)工時(shí)刻、加工位置等因素的函數(shù)描述。若工件的加工時(shí)間由其開(kāi)工時(shí)刻的分段線性函數(shù)和階梯函數(shù)刻畫(huà)，則稱其具有分段惡化效應(yīng)。此類問(wèn)題較之傳統(tǒng)調(diào)度問(wèn)題更加復(fù)雜，絕大多數(shù)是NP-hard的，通常無(wú)法在合理的時(shí)間內(nèi)求得最優(yōu)解，對(duì)這類調(diào)度問(wèn)題設(shè)計(jì)有效的調(diào)度優(yōu)化方法具有重要的理論和現(xiàn)實(shí)意義。
　　本文研究了分段線性惡化和階梯惡化這兩類效應(yīng)作用下的四個(gè)生產(chǎn)調(diào)度問(wèn)題，給出了它們的復(fù)雜性分析。由于這些問(wèn)題均是NP

3、-hard的，難以在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解，為此基于最優(yōu)調(diào)度方案的結(jié)構(gòu)特征和性質(zhì)分析，設(shè)計(jì)了啟發(fā)式調(diào)度優(yōu)化算法。論文的主要研究?jī)?nèi)容有:
　　(1)研究了分段線性惡化效應(yīng)作用下以最大完工時(shí)間最小化為目標(biāo)的單機(jī)調(diào)度問(wèn)題。此問(wèn)題是強(qiáng)NP-hard的，無(wú)法通過(guò)多項(xiàng)式算法求解。在最優(yōu)解的結(jié)構(gòu)特征分析的基礎(chǔ)上，提出了基于SPT排序規(guī)則的啟發(fā)式算法DSPT-PI，同時(shí)引入了遺傳算法以獲得更高質(zhì)量的解。該遺傳算法使用DSPT和隨機(jī)序列相結(jié)合的方式

4、產(chǎn)生初始種群，采用線性順序交叉算子和交換變異算子，并融入了成對(duì)互換搜索?；陔S機(jī)數(shù)值算例的仿真結(jié)果表明，啟發(fā)式算法DSPT-PI總體求解性能明顯好于已有的啟發(fā)式算法，遺傳算法的求解精度優(yōu)于模擬退火算法。
　　(2)對(duì)于具有階梯惡化效應(yīng)的單機(jī)調(diào)度問(wèn)題，研究了總延誤及總加權(quán)延誤兩種目標(biāo)函數(shù)。針對(duì)該問(wèn)題，建立了混合整數(shù)規(guī)劃模型，證明了總延誤最小化問(wèn)題為NP-hard的，分析了最優(yōu)解的性質(zhì)，設(shè)計(jì)了基于修正交貨期的啟發(fā)式算法IMDD和簡(jiǎn)單加

5、權(quán)搜索算法SWSP。同時(shí)還證明了總加權(quán)延誤最小化問(wèn)題為強(qiáng)NP-hard的，提出了通用變鄰域搜索算法GVNS進(jìn)行求解。利用隨機(jī)算例對(duì)算法的性能進(jìn)行了評(píng)估，分析發(fā)現(xiàn)GVNS能夠有效地求解該問(wèn)題，當(dāng)求解大規(guī)模問(wèn)題時(shí)給出的解的相對(duì)百分偏差為0.78％，相對(duì)平均偏差為0.81％。
　　(3)研究了具有階梯惡化效應(yīng)的并行機(jī)調(diào)度問(wèn)題，構(gòu)建了以總完工時(shí)間最小化為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，研究了不同建模方式下優(yōu)化模型的求解效率。針對(duì)該問(wèn)題，提出了

6、改進(jìn)加權(quán)組合搜索算法MWCSA，并設(shè)計(jì)了基于工件序列編碼的變鄰域搜索算法VNS。同時(shí)為了提高搜索速度，利用MWCSA為VNS產(chǎn)生初始解以形成改進(jìn)算法VNS+MWCSA?；陔S機(jī)算例的大量仿真結(jié)果表明，混合整數(shù)規(guī)劃模型的求解效率依賴于惡化工期的取值區(qū)間，VNS+MWCSA算法的性能優(yōu)于其他算法。
　　(4)研究了帶調(diào)整時(shí)間和階梯惡化效應(yīng)的并行機(jī)調(diào)度問(wèn)題，以最小化總延誤為目標(biāo)函數(shù)，建立了混合整數(shù)規(guī)劃模型。針對(duì)該問(wèn)題，提出了一種混合離散

7、布谷鳥(niǎo)搜索(HDCS)算法。該算法采用基于工件排列的離散編碼解碼方案，在種群初始化過(guò)程中融合了啟發(fā)式算法MBHG，在搜索過(guò)程中將種群劃分為普通解集和精英解集，對(duì)普通解實(shí)施基于CS的離散搜索，對(duì)精英解實(shí)施基于變鄰域下降的局部搜索。為了保持種群的多樣性，對(duì)部分個(gè)體采用了Restarting策略。算例求解結(jié)果表明混合算法HDCS是十分有效的，其求解效率受惡化工期取值的影響極小。
　　本文針對(duì)分段惡化效應(yīng)作用下的生產(chǎn)過(guò)程，以單機(jī)和同速并行