本文關(guān)鍵詞：一個(gè)特殊資源約束項(xiàng)目調(diào)度問(wèn)題模型及其優(yōu)化算法研究

  更多相關(guān)文章： 資源約束項(xiàng)目調(diào)度問(wèn)題 工位約束 串行進(jìn)度生成機(jī)制 迭代局部搜索 最大最小螞蟻系統(tǒng)

【摘要】：項(xiàng)目調(diào)度問(wèn)題在企業(yè)生產(chǎn)中有著很重要的作用,與生產(chǎn)效率、成本密切相關(guān)。由于企業(yè)生產(chǎn)過(guò)程的多樣性,經(jīng)典資源約束項(xiàng)目調(diào)度問(wèn)題(RCPSP)在實(shí)際生產(chǎn)中并不適用,所以,本文基于某企業(yè)的實(shí)際需求,在RCPSP基礎(chǔ)上加入了工位、工件等新的概念,增加了工位對(duì)可更新資源、工件加工的約束,設(shè)定最小化總流程時(shí)間和最小化總偏差時(shí)間為求解目標(biāo),提出了一個(gè)新的項(xiàng)目調(diào)度問(wèn)題模型——特殊資源約束項(xiàng)目調(diào)度問(wèn)題(SRCPSP),用以解決實(shí)際調(diào)度問(wèn)題。由于RCPSP是NP-hard問(wèn)題,而SRCPSP約束更為復(fù)雜,所以,只能使用啟發(fā)式算法進(jìn)行求解。本文首先使用基于串行進(jìn)度生成機(jī)制和優(yōu)先規(guī)則的啟發(fā)式算法對(duì)SRCPSP進(jìn)行求解,提出了三大類規(guī)則分別用于選擇工位、選擇資源和選擇工序,實(shí)驗(yàn)表明該算法可以快速生成一個(gè)初始可行解。然后,在此基礎(chǔ)上,對(duì)初始解進(jìn)行優(yōu)化算法研究。首先,本文實(shí)驗(yàn)了使用迭代局部搜索的方法,研究了使用迭代局部搜索時(shí)解的表示方式、鄰域結(jié)構(gòu)、擾動(dòng)策略等,然而研究表明,由于工件在工位間移動(dòng)的巨大時(shí)間代價(jià),迭代局部搜索并不適用于帶工位約束的項(xiàng)目調(diào)度問(wèn)題。之后,考慮到工序的調(diào)度主要是合適的工位和資源,所以本文實(shí)驗(yàn)了為工序隨機(jī)選擇工位和資源,結(jié)果表明,隨機(jī)選擇工位可以產(chǎn)生更好的結(jié)果。根據(jù)此結(jié)果,本文將蟻群優(yōu)化算法——最大最小螞蟻系統(tǒng)(MMAS)——應(yīng)用到工位選擇上,并用實(shí)驗(yàn)確定了蟻群算法中各項(xiàng)參數(shù)。實(shí)驗(yàn)表明,使用最大最小螞蟻系統(tǒng)優(yōu)化工位選擇過(guò)程的方法是切實(shí)有效的,并且在生成相同數(shù)量解的情況下,相較于隨機(jī)選擇是穩(wěn)定較優(yōu)的。因此,對(duì)于本文提出的SRCPSP模型,設(shè)計(jì)的基于MMAS的優(yōu)化算法具有很好的求解效果,將MMAS應(yīng)用到工位選擇上是合理有效的。
【關(guān)鍵詞】：資源約束項(xiàng)目調(diào)度問(wèn)題 工位約束 串行進(jìn)度生成機(jī)制 迭代局部搜索 最大最小螞蟻系統(tǒng)
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-19
• 1.1 研究背景及意義11-15
• 1.1.1 基本概念及約束11-13
• 1.1.2 RCPSP模型13
• 1.1.3 求解算法13-15
• 1.1.4 RCPSP局限性及本文研究意義15
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀15-18
• 1.2.1 RCPSP模型擴(kuò)展研究現(xiàn)狀15-17
• 1.2.2 算法研究現(xiàn)狀17-18
• 1.3 論文主要內(nèi)容和組織結(jié)構(gòu)18
• 1.4 本章小結(jié)18-19
• 2 特殊資源約束項(xiàng)目調(diào)度問(wèn)題模型19-28
• 2.1 環(huán)境數(shù)據(jù)19-21
• 2.1.1 工件20
• 2.1.2 工位20
• 2.1.3 資源20-21
• 2.1.4 工序21
• 2.2 約束關(guān)系21-24
• 2.2.1 資源約束22-23
• 2.2.2 工序約束23-24
• 2.3 問(wèn)題目標(biāo)24
• 2.4 模型舉例24-27
• 2.5 本章小結(jié)27-28
• 3 基于優(yōu)先規(guī)則的SSGS啟發(fā)式算法28-36
• 3.1 基本概念及定義28-29
• 3.2 算法總體流程29-30
• 3.3 優(yōu)先規(guī)則30-33
• 3.3.1 工位選擇規(guī)則30-31
• 3.3.2 資源選擇規(guī)則31
• 3.3.3 工序選擇規(guī)則31-32
• 3.3.4 解鎖規(guī)則32-33
• 3.4 輸入及輸出數(shù)據(jù)格式33
• 3.4.1 輸入數(shù)據(jù)33
• 3.4.2 輸出數(shù)據(jù)33
• 3.5 本章小結(jié)33-36
• 4 基于迭代局部搜索的優(yōu)化算法36-45
• 4.1 迭代局部搜索算法36-37
• 4.2 SRCPSP問(wèn)題的迭代局部搜索優(yōu)化算法設(shè)計(jì)37-42
• 4.2.1 解的表示37-38
• 4.2.2 鄰域結(jié)構(gòu)38-39
• 4.2.3 擾動(dòng)策略39-40
• 4.2.4 算法總流程設(shè)計(jì)40-42
• 4.3 實(shí)驗(yàn)與結(jié)果分析42-44
• 4.4 本章小結(jié)44-45
• 5 基于蟻群算法的優(yōu)化算法45-61
• 5.1 隨機(jī)抽樣算法45-49
• 5.1.1 工位隨機(jī)選擇算法47
• 5.1.2 資源隨機(jī)選擇算法47
• 5.1.3 實(shí)驗(yàn)驗(yàn)證及分析47-49
• 5.2 蟻群算法49-56
• 5.2.1 蟻群優(yōu)化算法49-50
• 5.2.2 基于MMAS的優(yōu)化算法設(shè)計(jì)與實(shí)現(xiàn)50-52
• 5.2.3 基于MMAS的優(yōu)化算法參數(shù)選擇52-56
• 5.3 實(shí)驗(yàn)結(jié)果與分析56-60
• 5.3.1 測(cè)試用例描述56-57
• 5.3.2 性能和可行性測(cè)試57-59
• 5.3.3 MMAS優(yōu)化算法與隨機(jī)算法對(duì)比59-60
• 5.4 本章小結(jié)60-61
• 6 總結(jié)與展望61-63
• 6.1 本文總結(jié)61-62
• 6.2 展望及今后的工作62-63
• 參考文獻(xiàn)63-67
• 作者簡(jiǎn)歷及攻讀碩士學(xué)位期間取得的研究成果67-69
• 學(xué)位論文數(shù)據(jù)集69

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 宋紅星;曹文彬;;基于雙種群蟻群算法的多目標(biāo)資源受限項(xiàng)目調(diào)度問(wèn)題研究[J];信息系統(tǒng)工程;2010年04期

2 程序;吳澄;;一種復(fù)雜項(xiàng)目調(diào)度問(wèn)題的混合智能算法[J];計(jì)算機(jī)集成制造系統(tǒng);2006年04期

3 徐進(jìn);費(fèi)少梅;張樹(shù)有;施岳定;;自適應(yīng)粒子群求解資源動(dòng)態(tài)分配項(xiàng)目調(diào)度問(wèn)題[J];計(jì)算機(jī)集成制造系統(tǒng);2011年08期

4 雒興剛;汪定偉;唐加福;;任務(wù)可拆分項(xiàng)目調(diào)度問(wèn)題[J];東北大學(xué)學(xué)報(bào);2006年09期

5 宗硯;劉瓊;張超勇;朱海平;;考慮資源傳遞時(shí)間的多項(xiàng)目調(diào)度問(wèn)題[J];計(jì)算機(jī)集成制造系統(tǒng);2011年09期

6 孫曉雅;林焰;;任務(wù)可定點(diǎn)拆分的資源受限項(xiàng)目調(diào)度問(wèn)題研究[J];微電子學(xué)與計(jì)算機(jī);2012年07期

7 張維存;康凱;;蟻群-粒子群算法求解多模式資源受限項(xiàng)目調(diào)度問(wèn)題[J];計(jì)算機(jī)工程與應(yīng)用;2007年34期

8 劉敏;代成琴;王宇航;;資源受限的項(xiàng)目調(diào)度問(wèn)題的求解算法[J];自動(dòng)化技術(shù)與應(yīng)用;2008年06期

9 盧睿;李林瑛;;一種求解反應(yīng)式項(xiàng)目調(diào)度問(wèn)題的啟發(fā)式方法[J];系統(tǒng)仿真學(xué)報(bào);2011年02期

10 孫曉雅;林焰;;人工蜂群算法求解任務(wù)可拆分項(xiàng)目調(diào)度問(wèn)題[J];微電子學(xué)與計(jì)算機(jī);2011年11期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前3條

1 丁雪楓;尤建新;;多模式資源受限項(xiàng)目調(diào)度問(wèn)題的混合優(yōu)化算法研究[A];第十四屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集(上冊(cè))[C];2012年

2 劉艷秋;張穎;汪定偉;王福利;;基于GA的RCPSP可靠性優(yōu)化方法研究[A];2001年中國(guó)智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2001年

3 周楷;何正文;;周期性支付的多模式Max-npv項(xiàng)目調(diào)度問(wèn)題研究[A];中國(guó)企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會(huì)論文集[C];2008年

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

1 王宏;求解資源受限項(xiàng)目調(diào)度問(wèn)題算法的研究[D];天津大學(xué);2005年

2 鄧林義;資源受限的項(xiàng)目調(diào)度問(wèn)題及其應(yīng)用研究[D];大連理工大學(xué);2008年

3 陳衛(wèi)明;動(dòng)態(tài)環(huán)境下產(chǎn)品開(kāi)發(fā)項(xiàng)目調(diào)度問(wèn)題及其求解研究[D];華中科技大學(xué);2011年

4 吳兵;柔性資源受限的多模式項(xiàng)目調(diào)度問(wèn)題研究[D];武漢理工大學(xué);2008年

5 彭武良;面向產(chǎn)品開(kāi)發(fā)的項(xiàng)目調(diào)度問(wèn)題及項(xiàng)目管理系統(tǒng)研究[D];東北大學(xué);2008年

6 李詩(shī)嫻;基于凈現(xiàn)值的資源受限型項(xiàng)目調(diào)度問(wèn)題研究[D];天津大學(xué);2012年

7 賈艷;資源受限項(xiàng)目調(diào)度問(wèn)題的仿真優(yōu)化方法及其應(yīng)用研究[D];華中科技大學(xué);2012年

8 應(yīng)瑛;不確定資源約束下項(xiàng)目調(diào)度問(wèn)題研究[D];浙江大學(xué);2010年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 李遠(yuǎn)見(jiàn);幾種改進(jìn)的智能算法及其應(yīng)用[D];安徽師范大學(xué);2015年

2 段向陽(yáng);基于遺傳算法的資源約束項(xiàng)目調(diào)度問(wèn)題優(yōu)化及應(yīng)用研究[D];湖南工業(yè)大學(xué);2015年

3 栗明威;一個(gè)特殊資源約束項(xiàng)目調(diào)度問(wèn)題模型及其優(yōu)化算法研究[D];北京交通大學(xué);2016年

4 張冠群;基于蟻群算法的多模式資源受限項(xiàng)目調(diào)度問(wèn)題研究[D];湖南大學(xué);2009年

5 傅奧;多目標(biāo)資源受限項(xiàng)目調(diào)度問(wèn)題蟻群算法研究[D];浙江大學(xué);2008年

6 蒲娟;多目標(biāo)模糊資源受限項(xiàng)目調(diào)度問(wèn)題研究[D];鄭州大學(xué);2012年

7 薄銀利;基于模塊化外包的項(xiàng)目調(diào)度問(wèn)題研究[D];蘭州大學(xué);2011年

8 劉志霞;資源受限項(xiàng)目調(diào)度問(wèn)題及其任務(wù)擾動(dòng)的干擾管理研究[D];沈陽(yáng)工業(yè)大學(xué);2011年

9 陳俊波;考慮施工設(shè)備租賃的項(xiàng)目調(diào)度問(wèn)題研究[D];華中科技大學(xué);2009年

10 劉雅婷;人力資源受限項(xiàng)目調(diào)度問(wèn)題研究[D];華中科技大學(xué);2007年

，

本文編號(hào)：759811