雙機(jī)流水車間問(wèn)題基于沖突窗口的滾動(dòng)調(diào)度算法.pdf

1、生產(chǎn)調(diào)度問(wèn)題存在于大量實(shí)際制造業(yè)中，構(gòu)成了各種先進(jìn)制造模式共同關(guān)注的核心內(nèi)容和重要組成部分，對(duì)于車輛調(diào)度、鐵路調(diào)度、航空調(diào)度、企業(yè)多項(xiàng)目管理的等資源調(diào)度問(wèn)題，也大多可以利用生產(chǎn)調(diào)度的基本原理，可以說(shuō)，生產(chǎn)調(diào)度這一基本原型應(yīng)用領(lǐng)域是非常廣泛的。同時(shí)，生產(chǎn)調(diào)度問(wèn)題也是一類非常典型的組合優(yōu)化問(wèn)題，在求解方面具備相當(dāng)?shù)碾y度，其計(jì)算量通常隨調(diào)度問(wèn)題規(guī)模呈指數(shù)增長(zhǎng)，絕大多數(shù)調(diào)度問(wèn)題都屬于NP完備問(wèn)題。因此，無(wú)論在實(shí)際工業(yè)生產(chǎn)方面，還是在理論學(xué)術(shù)研究

2、方面，對(duì)生產(chǎn)調(diào)度問(wèn)題的研究都有著非常重要的意義。
　　生產(chǎn)調(diào)度的算法可簡(jiǎn)單概括為精確算法、啟發(fā)式算法和人工智能算法。精確算法能獲得最優(yōu)解，但是計(jì)算效率低，遇到大規(guī)模的復(fù)雜問(wèn)題，這種算法有時(shí)甚至難以獲得解。由此而發(fā)展起來(lái)的啟發(fā)式算法則是利用啟發(fā)式規(guī)則，在較短的時(shí)間內(nèi)便能獲得相對(duì)不錯(cuò)的解，目前已擴(kuò)展了相當(dāng)多的啟發(fā)式規(guī)則。隨著科技進(jìn)步，人工智能算法是目前研究較為集中的一種算法，它具有搜素效率高，適應(yīng)性強(qiáng)和魯棒性能好等特點(diǎn)，但是這類算法也

3、不能保證獲得最優(yōu)解。由于流水車間的特點(diǎn)，本文主要著眼于啟發(fā)式算法。
　　在啟發(fā)式算法下，本文采用滾動(dòng)調(diào)度策略，研究了流水車間雙機(jī)調(diào)度問(wèn)題。滾動(dòng)調(diào)度策略下，將一個(gè)大規(guī)模問(wèn)題分解為許多子問(wèn)題，可使問(wèn)題規(guī)模大大減小，有效縮短求解時(shí)間。滾動(dòng)調(diào)度多用于單機(jī)情形，此次將其應(yīng)用于流水車間雙機(jī)情形，同時(shí)跳出傳統(tǒng)的滾動(dòng)調(diào)度策略框架，即基于時(shí)間的滾動(dòng)調(diào)度和基于工件數(shù)的滾動(dòng)調(diào)度，提出本文新的滾動(dòng)調(diào)度算法——基于沖突窗口的滾動(dòng)調(diào)度算法。該算法充分利用了流

4、水車間雙機(jī)問(wèn)題的特點(diǎn)，結(jié)合了經(jīng)典的Johnson規(guī)則。
　　在本文中描述了沖突窗口的形成，子問(wèn)題的最優(yōu)調(diào)度，列述了算法的基本思路和步驟。另外，本文采用大規(guī)模仿真的方法，將本算法與另三種算法，即基于時(shí)間的滾動(dòng)調(diào)度算法、基于工件數(shù)的滾動(dòng)調(diào)度算法和貪婪Johnson算法進(jìn)行了大量對(duì)比，這三類算法是流水車間比較傳統(tǒng)的算法。仿真模擬了各算法在工件數(shù)為10到500個(gè)時(shí)的具體表現(xiàn)，并通過(guò)控制參數(shù)使得工件的到達(dá)呈現(xiàn)不同的緊密程度。最終實(shí)驗(yàn)結(jié)果顯示

5、，除了工件數(shù)為10時(shí)，基于時(shí)間的滾動(dòng)調(diào)度算法比基于沖突窗口的滾動(dòng)調(diào)度求解的質(zhì)量更優(yōu)，其余情況下，基于沖突窗口的滾動(dòng)調(diào)度平均表現(xiàn)都是最好的，另外本論文提出的算法在計(jì)算量上相對(duì)另兩種滾動(dòng)調(diào)度算法具有絕對(duì)的優(yōu)勢(shì)，即使解決500個(gè)工件的大規(guī)模問(wèn)題，效率也非常高，貪婪Johnson算法雖然在時(shí)間上也具有優(yōu)勢(shì)，但在四種算法中解的質(zhì)量最差。
　　最后本文將基于沖突窗口的滾動(dòng)調(diào)度應(yīng)用于帶有季節(jié)性需求特征的具體實(shí)例中，以探討其實(shí)際應(yīng)用價(jià)值。通過(guò)仿真