【摘要】：研究了流水機(jī)環(huán)境下最小化總誤工損失的調(diào)度問題。流水機(jī)調(diào)度指的是n個(gè)工件需要m臺(tái)機(jī)器加工,每個(gè)工件需要m道工序,每道工序需要不同的機(jī)器;n個(gè)工件在m臺(tái)機(jī)器上的加工順序相同。工件的誤工損失是與交付期有關(guān)的一種懲罰量,其數(shù)值正比于工件滯后于其交付期加工的部分。針對(duì)該問題不同模型,分別設(shè)計(jì)了分枝定界算法求解其小規(guī)模運(yùn)算實(shí)例,以及遺傳算法求解大規(guī)模實(shí)例。對(duì)于兩臺(tái)流水機(jī)模型,重新分析了2006年發(fā)表的分枝定界算法,利用反例法指出其下界設(shè)計(jì)中的錯(cuò)誤;然后給出了新的計(jì)算下界方法,給出一個(gè)新的分枝定界算法。該算法利用遺傳算法獲得初始解,并利用上下界剪枝規(guī)則、節(jié)點(diǎn)間的支配規(guī)則去掉無(wú)效節(jié)點(diǎn),縮小搜索規(guī)模。對(duì)于多臺(tái)流水機(jī)模型,擴(kuò)展了上述的遺傳算法。根據(jù)問題特性,定義了染色體的編碼方式、交叉和變異規(guī)則,以及算法終止條件。對(duì)于多臺(tái)流水機(jī)模型,問題規(guī)模稍微增大,精確算法很難在滿意的時(shí)間內(nèi)找到最優(yōu)解,甚至不可能找到最優(yōu)解;因此,本文用遺傳算法求所研究問題的近似解,并與其它的啟發(fā)式算法的實(shí)驗(yàn)結(jié)果做比較,證明了遺傳算法相比于其它啟發(fā)式算法能更好的改善問題的初始解。實(shí)驗(yàn)數(shù)據(jù)表明,上述兩個(gè)算法在處理小規(guī)模實(shí)例和中大規(guī)模實(shí)例過程中性能表現(xiàn)良好。帶下界規(guī)則的分枝定界算法能有效地去除搜索樹中的無(wú)效分枝,支配規(guī)則可以有效的去除無(wú)效節(jié)點(diǎn),顯著地提高了分支定界算法的搜索效率。遺傳算法能夠快速求解大規(guī)模算例,且性能遠(yuǎn)優(yōu)于那些簡(jiǎn)單的啟發(fā)式規(guī)則,能夠?yàn)榍蠼獯笠?guī)模問題算例時(shí)提供較好初始解。
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 桂洪照;;幾種具有代表性的啟發(fā)式算法研究[J];電子制作;2016年02期

2 王芳,施國(guó)洪;商貿(mào)服務(wù)業(yè)選址決策研究——一種基于阿德蘭啟發(fā)式算法的選址方法[J];江蘇商論;2004年07期

3 陶光遠(yuǎn);周佩德;王強(qiáng);;最優(yōu)運(yùn)輸徑路選擇的啟發(fā)式算法[J];南京工學(xué)院學(xué)報(bào);1987年06期

4 許杰鋒;;客車調(diào)度問題(BSP)的數(shù)學(xué)模型及一種新的啟發(fā)式算法[J];上海交通大學(xué)學(xué)報(bào);1988年06期

5 邢琳;;一種啟發(fā)式識(shí)別被積函數(shù)算法的設(shè)計(jì)與實(shí)現(xiàn)[J];中南礦冶學(xué)院學(xué)報(bào);1988年01期

6 郭耀煌,范莉莉;貨運(yùn)汽車調(diào)度的一種啟發(fā)式算法[J];系統(tǒng)工程;1989年01期

7 楊英杰;;單體型裝配問題的啟發(fā)式算法研究[J];數(shù)字技術(shù)與應(yīng)用;2017年01期

8 陳燕;謝琪琦;劉詠;崔耀東;;圓形件下料順序分組啟發(fā)式算法的設(shè)計(jì)與實(shí)現(xiàn)[J];圖學(xué)學(xué)報(bào);2017年01期

9 潘立軍;符卓;;求解帶硬時(shí)間窗車輛路徑問題的時(shí)差插入啟發(fā)式算法[J];計(jì)算機(jī)應(yīng)用;2012年11期

10 高尚,陳鋼;可靠性優(yōu)化的一種新的啟發(fā)式算法[J];工程設(shè)計(jì)學(xué)報(bào);2004年03期

相關(guān)會(huì)議論文 前10條

1 馮德鴻;唐加福;郭琦;李輝;;訂貨批量問題改進(jìn)的相關(guān)策略啟發(fā)式算法與仿真分析[A];2007系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2007年

2 羅守成;唐國(guó)春;;二維集裝箱問題的一個(gè)啟發(fā)式算法[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

3 劉嘉敏;馬廣煜;黃有群;;基于組合的三維集裝箱裝入啟發(fā)式算法的研究[A];全國(guó)第13屆計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)（CAD/CG）學(xué)術(shù)會(huì)議論文集[C];2004年

4 戴娜;肖杰;邸瑞華;;異構(gòu)計(jì)算環(huán)境下任務(wù)調(diào)度模型的啟發(fā)式算法研究[A];2006年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集（三）[C];2006年

5 許爭(zhēng)爭(zhēng);;自有和租用車輛并存條件下基于協(xié)作的啟發(fā)式算法研究[A];第十九屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2017年

6 劉青松;孔云峰;黨蘭學(xué);王震;;元啟發(fā)式算法在校車路徑規(guī)劃中的應(yīng)用[A];第七屆全國(guó)地理學(xué)研究生學(xué)術(shù)年會(huì)論文摘要集[C];2012年

7 何正文;徐渝;;多模式項(xiàng)目支付進(jìn)度問題的優(yōu)化模型及啟發(fā)式算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

8 黃忠圣;;高等啟發(fā)式算法在桁架結(jié)構(gòu)優(yōu)化中的應(yīng)用[A];北京力學(xué)會(huì)第21屆學(xué)術(shù)年會(huì)暨北京振動(dòng)工程學(xué)會(huì)第22屆學(xué)術(shù)年會(huì)論文集[C];2015年

9 李兵;蔣慰孫;;改進(jìn)的遺傳算法及在一類組合優(yōu)化問題中的應(yīng)用[A];1995中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1995年

10 張建勇;李軍;;模糊需求VRP的一種Sweeping啟發(fā)式算法[A];第九屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2007年

相關(guān)重要報(bào)紙文章 前2條

1 羽中;啟發(fā)式算法的大能量[N];國(guó)家電網(wǎng)報(bào);2018年

2 褚會(huì)會(huì);建立數(shù)學(xué)模型 啟發(fā)式算法求解[N];東方煙草報(bào);2016年

相關(guān)博士學(xué)位論文 前10條

1 閆志遠(yuǎn);地理網(wǎng)絡(luò)分析中的并行啟發(fā)式算法研究[D];中國(guó)礦業(yè)大學(xué)(北京);2015年

2 古繼興;KOD多播技術(shù)與Steiner樹啟發(fā)式算法[D];上海交通大學(xué);2007年

3 董興業(yè);啟發(fā)式算法及其在同順序流水作業(yè)問題中的應(yīng)用[D];北京交通大學(xué);2008年

4 馬華偉;帶時(shí)間窗車輛路徑問題及其啟發(fā)式算法研究[D];合肥工業(yè)大學(xué);2008年

5 胡大偉;設(shè)施定位和車輛路線問題模型及其啟發(fā)式算法研究[D];長(zhǎng)安大學(xué);2008年

6 石文;空中交通管理優(yōu)化問題研究[D];天津大學(xué);2014年

7 楊玉珍;基于元啟發(fā)式算法的帶生產(chǎn)約束作業(yè)車間調(diào)度問題若干研究[D];華東理工大學(xué);2014年

8 鄧冠龍;基于元啟發(fā)式算法的調(diào)度問題若干研究[D];華東理工大學(xué);2012年

9 鄭君璽;一類混合生產(chǎn)線調(diào)度與數(shù)值仿真技術(shù)的研究[D];華南理工大學(xué);2016年

10 李常敏;兩層規(guī)劃的逼近理論及算法研究[D];復(fù)旦大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 鄭志祥;基于元啟發(fā)式算法的進(jìn)場(chǎng)決策支持研究[D];南京航空航天大學(xué);2018年

2 王中玉;誤工最小化流水調(diào)度精確及啟發(fā)式算法研究[D];大連理工大學(xué);2018年

3 郭竹峰;基于變量權(quán)重的約束滿足問題啟發(fā)式算法研究[D];吉林大學(xué);2018年

4 苗曉燕;基于啟發(fā)式算法邊坡及支擋結(jié)構(gòu)穩(wěn)定性分析方法[D];湖南大學(xué);2017年

5 霍超;求解多目標(biāo)無(wú)約束二元二次規(guī)劃問題的元啟發(fā)式算法研究[D];電子科技大學(xué);2018年

6 羅云鳳;基于啟發(fā)式智能搜索的貨運(yùn)列車節(jié)能優(yōu)化研究[D];江西理工大學(xué);2018年

7 江韻;《大數(shù)據(jù)元啟發(fā)式算法》（第5章與第8章）翻譯實(shí)踐報(bào)告[D];青島科技大學(xué);2018年

8 邊哲永;基于兩種改進(jìn)策略的亞啟發(fā)式算法求解路徑相關(guān)問題研究[D];天津大學(xué);2016年

9 劉暢;基于混合啟發(fā)式算法的單線公交車輛調(diào)度問題研究[D];北京交通大學(xué);2016年

10 姜毅;擾動(dòng)型超啟發(fā)式算法的適應(yīng)度地貌分析[D];大連理工大學(xué);2013年

，

本文編號(hào)：2649345