存儲容量受限的排列排序流水車間調(diào)度問題的鄰域搜索算法.pdf

1、東北大學(xué)碩士學(xué)位論文摘要摘要甘毛、1，.衛(wèi)e.1....‘.1.........月國哺JJ一僑儲容量受限(FIS)的排列排序流水車間調(diào)度問題是指對n個工件的排序，這些工件要在m臺機(jī)器上以相同順序進(jìn)行加工，在每相鄰兩臺機(jī)器之間都存在一個容量固定的先進(jìn)先出的存儲罐。存儲容量受限的車間調(diào)度問題在化工生產(chǎn)中具有很強(qiáng)的應(yīng)用背景。由于受到存儲容量的限制，它比一般flowshop調(diào)度問題要復(fù)雜得多。該調(diào)度問題己被證明是NP一難問題。研究這類問題的快速

2、可行的近優(yōu)算法是一個挑戰(zhàn)性的研究課!題，近年來己經(jīng)引起了國際學(xué)術(shù)界的關(guān)注了本文針對FIS排列排序流水車間調(diào)度問題完成時間(makespan)為目標(biāo)函數(shù)的數(shù)學(xué)模型。建立了以最小化最大提出并證明了新的改進(jìn)鄰域block特性，基于改進(jìn)鄰域block特性作為鄰域搜索策略構(gòu)造了禁忌搜索算法，通過實驗證明了算法的有效性，并分析了算法性能和問題結(jié)構(gòu)、規(guī)模之間的關(guān)系。根據(jù)該問題的有限存儲性質(zhì)，提出了適用于此類問題的計算目標(biāo)函數(shù)的新方法一正向和逆向棍合計

3、算方法，根據(jù)相鄰兩次移動之間目標(biāo)函數(shù)計算上的繼承性，減少了獲得目標(biāo)函數(shù)的計算量，從而加快了算法運行速度。通過實驗，獲得了加速算法的改進(jìn)幅度。一協(xié)該問”“計并實施了基于隨機(jī)kick策略的迭代局域搜索算法，對算法中的kick移動數(shù)和鄰域選擇，通過大量的仿真實驗進(jìn)行了優(yōu)化配置。設(shè)計并實現(xiàn)了兩種混合算法。第一種混合算法是基于改進(jìn)鄰域block特性和加速策略構(gòu)成的禁忌搜索算法第二種混合算法是嵌入迭代局域搜索策略的改進(jìn)禁忌搜索算法，通過實驗證明，兩

4、種混合算法分別優(yōu)于該問題的benchmark算法，前一種混合算法略優(yōu)于后一種混合算法。今關(guān)鍵詞:有限存儲，索算法，混合算法流水車間調(diào)度，改進(jìn)恤索算法，迭代局域搜—一，，一一一飛蕩二..峨.....峨口思欲急優(yōu)丁而獲藤刃禱1涵頤雨獷下下.萬東北大學(xué)碩士學(xué)位論文consecutivemoves.摘要ComputationalresultsshowthedegreeoftheimprovementAniterativeneighborhood

5、searchalgorithmisdesignedandimplementedwhichisbasedonrandomkickstrategy.Thekicknumberandthechoicesofneighborhoodinthealgorithmsareconfiguredoptimallybycomputationalexperiments.Twohybridalgorithmsareconstructed.Oneistheta

6、busearchalgorithmbasedonimprovedblockpropertiesoftheneighborhoodandspeedupsstrategyandtheotherisimprovedtabusearchalgorithminwhichtheiterativeneighborhoodsearchstrategyisembedded.Computationalexperimentsshow川門川，十IJJdesJ刁

7、.esJ月JJJJI........‘..已硬...。......thatbothofthealgorithmsaresuperiortothebenchmarkonemoreoverthetngformerisabitbetterthanthelatterKeywords:finiteintermediatestoragepermutationflowshopschedulimprovedtabusearchalgorithmiter