本文關(guān)鍵詞：雙機(jī)流水車間問題基于沖突窗口的滾動(dòng)調(diào)度算法

  更多相關(guān)文章： 流水車間 滾動(dòng)調(diào)度 沖突窗口 大規(guī)模仿真

【摘要】：生產(chǎn)調(diào)度問題存在于大量實(shí)際制造業(yè)中,構(gòu)成了各種先進(jìn)制造模式共同關(guān)注的核心內(nèi)容和重要組成部分,對(duì)于車輛調(diào)度、鐵路調(diào)度、航空調(diào)度、企業(yè)多項(xiàng)目管理的等資源調(diào)度問題,也大多可以利用生產(chǎn)調(diào)度的基本原理,可以說,生產(chǎn)調(diào)度這一基本原型應(yīng)用領(lǐng)域是非常廣泛的。同時(shí),生產(chǎn)調(diào)度問題也是一類非常典型的組合優(yōu)化問題,在求解方面具備相當(dāng)?shù)碾y度,其計(jì)算量通常隨調(diào)度問題規(guī)模呈指數(shù)增長,絕大多數(shù)調(diào)度問題都屬于NP完備問題。因此,無論在實(shí)際工業(yè)生產(chǎn)方面,還是在理論學(xué)術(shù)研究方面,對(duì)生產(chǎn)調(diào)度問題的研究都有著非常重要的意義。生產(chǎn)調(diào)度的算法可簡單概括為精確算法、啟發(fā)式算法和人工智能算法。精確算法能獲得最優(yōu)解,但是計(jì)算效率低,遇到大規(guī)模的復(fù)雜問題,這種算法有時(shí)甚至難以獲得解。由此而發(fā)展起來的啟發(fā)式算法則是利用啟發(fā)式規(guī)則,在較短的時(shí)間內(nèi)便能獲得相對(duì)不錯(cuò)的解,目前已擴(kuò)展了相當(dāng)多的啟發(fā)式規(guī)則。隨著科技進(jìn)步,人工智能算法是目前研究較為集中的一種算法,它具有搜素效率高,適應(yīng)性強(qiáng)和魯棒性能好等特點(diǎn),但是這類算法也不能保證獲得最優(yōu)解。由于流水車間的特點(diǎn),本文主要著眼于啟發(fā)式算法。在啟發(fā)式算法下,本文采用滾動(dòng)調(diào)度策略,研究了流水車間雙機(jī)調(diào)度問題。滾動(dòng)調(diào)度策略下,將一個(gè)大規(guī)模問題分解為許多子問題,可使問題規(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)度算法。該算法充分利用了流水車間雙機(jī)問題的特點(diǎn),結(jié)合了經(jīng)典的Johnson規(guī)則。在本文中描述了沖突窗口的形成,子問題的最優(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),并通過控制參數(shù)使得工件的到達(dá)呈現(xiàn)不同的緊密程度。最終實(shí)驗(yàn)結(jié)果顯示,除了工件數(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ī)模問題,效率也非常高,貪婪Johnson算法雖然在時(shí)間上也具有優(yōu)勢(shì),但在四種算法中解的質(zhì)量最差。最后本文將基于沖突窗口的滾動(dòng)調(diào)度應(yīng)用于帶有季節(jié)性需求特征的具體實(shí)例中,以探討其實(shí)際應(yīng)用價(jià)值。通過仿真的方法,基于沖突窗口的滾動(dòng)調(diào)度相較于基于時(shí)間的滾動(dòng)調(diào)度能更好地處理需求波動(dòng)大的季節(jié)性產(chǎn)品,其求解速度更快,求解質(zhì)量更好。
【學(xué)位授予單位】：東華大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TB497

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前6條

1 方劍,席裕庚;基于遺傳算法的滾動(dòng)調(diào)度策略[J];控制理論與應(yīng)用;1997年04期

2 ;Rolling optimization algorithm based on collision window for single machine scheduling problem[J];Journal of Systems Engineering and Electronics;2005年04期

3 錢斌;王凌;黃德先;江永亨;王雄;;動(dòng)態(tài)零等待流水線調(diào)度問題的滾動(dòng)策略及優(yōu)化算法[J];控制與決策;2009年04期

4 唐聃;黃健;;流水車間調(diào)度問題的啟發(fā)式算法研究[J];電子科技大學(xué)學(xué)報(bào);2013年06期

5 黃健倉;;建設(shè)企業(yè)多項(xiàng)目管理中的資源調(diào)度問題研究[J];中國軟科學(xué);2016年01期

6 范華麗;熊禾根;蔣國璋;李公法;;動(dòng)態(tài)車間作業(yè)調(diào)度問題中調(diào)度規(guī)則算法研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2016年03期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 劉延風(fēng);置換流水車間調(diào)度問題的幾種智能算法[D];西安電子科技大學(xué);2012年

，

本文編號(hào)：1227240