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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 胡大偉;設(shè)施定位和車輛路線問題模型及其啟發(fā)式算法研究[D];長安大學(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ā)式算法的進場決策支持研究[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)無約束二元二次規(guī)劃問題的元啟發(fā)式算法研究[D];電子科技大學(xué);2018年

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

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

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

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

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

，

本文編號：2649345