發(fā)布時間：2018-07-07 16:12

  本文選題：適應(yīng)度地形 + Logistic模型�。� 參考：《華中科技大學(xué)》2012年碩士論文

【摘要】：作業(yè)車間調(diào)度是車間調(diào)度中一類典型的問題，其研究方法與成果已被運(yùn)用于眾多其它類型調(diào)度問題以及實(shí)際的生產(chǎn)運(yùn)作中，針對作業(yè)車間調(diào)度問題的特性研究和算法設(shè)計(jì)具有重要的意義。本文從適應(yīng)度地形理論出發(fā)，從搜索空間地形的分布和結(jié)構(gòu)兩方面來探討作業(yè)車間調(diào)度問題的本質(zhì)特性和影響因素，并據(jù)此設(shè)計(jì)出高效的調(diào)度優(yōu)化算法。 本文首先提出了基于Logistic模型的適應(yīng)度地形研究方法，，該模型能有效地區(qū)分不同的問題實(shí)例。在使用該方法來研究問題基本屬性對適應(yīng)度地形分布特性的影響中發(fā)現(xiàn)：問題的形狀約束會對地形分布產(chǎn)生巨大影響，隨著工件數(shù)對機(jī)器數(shù)比例的提升，問題的求解難度會呈現(xiàn)“易—難—易”的變化規(guī)律，問題加工路徑約束的增多會使地形崎嶇而難求解，而加工時間的影響比較微弱。實(shí)例測試表明，該方法相比以往研究方法能更好地反映問題的適應(yīng)度地形特性。 接著使用局部搜索算法來研究問題適應(yīng)度地形的結(jié)構(gòu)特征，發(fā)現(xiàn)個體的搜索過程也會出現(xiàn)Logistic式的分布規(guī)律。分別使用2點(diǎn)交換鄰域和關(guān)鍵路徑插入鄰域的局部搜索算法來研究問題基本屬性對適應(yīng)度地形結(jié)構(gòu)特性的影響，結(jié)果表明：加工路徑約束會對地形結(jié)構(gòu)中盆地與峽谷的比例和性質(zhì)產(chǎn)生較大影響，而形狀和規(guī)模并未改變地形的結(jié)構(gòu)性質(zhì)。兩種鄰域策略所表現(xiàn)出來的不同地形結(jié)構(gòu)特征，則為算法的設(shè)計(jì)提供了思路。 基于前述研究結(jié)論，本文在廣義粒子群優(yōu)化模型框架下提出了粒子群優(yōu)化與變鄰域搜索的混合算法。使用本文提出的Logistic模型來挑選高效的鄰域組合策略，結(jié)果表明，基于交換的隨機(jī)全鄰域和基于插入的N5鄰域具有較好的組合效果。實(shí)例測試表明，該混合算法效果要優(yōu)于單一的鄰域搜索，LA系列的40個實(shí)例中，有38個可以求得最優(yōu)解，驗(yàn)證了所提出的算法的優(yōu)越性。 文章最后對全文進(jìn)行總結(jié)，并對作業(yè)車間調(diào)度和適應(yīng)度地形的研究進(jìn)行了展望。
[Abstract]:Job shop scheduling is a typical problem in job shop scheduling. Its research methods and achievements have been applied to many other scheduling problems and practical production operations. It is of great significance to study the characteristics and algorithm design of job shop scheduling problem. Based on the fitness terrain theory, this paper discusses the essential characteristics and influencing factors of job shop scheduling problem from the distribution and structure of search space terrain, and designs an efficient scheduling optimization algorithm. In this paper, we first propose a method for the study of fitness terrain based on Logistic model, which can effectively distinguish different problem cases. It is found that the shape constraint of the problem has a great influence on the topographic distribution with the increase of the number of jobs to the number of machines, and the effect of the basic properties of the problem on the distribution of the terrain is studied by using this method. The difficulty of solving the problem will present the law of "easy-difficult-easy". The increase of the constraint of processing path will make the terrain difficult and difficult to solve, but the influence of processing time is weak. The experimental results show that the proposed method can better reflect the fitness of the problem than the previous methods. Then the local search algorithm is used to study the structural characteristics of the fitness terrain and it is found that the logistic distribution is also found in the individual search process. The local search algorithms of 2-point exchange neighborhood and critical path insertion neighborhood are used to study the effect of the basic properties of the problem on the fitness of terrain structure. The results show that the processing path constraint has a great influence on the ratio and nature of the basin to the canyon in the topographic structure, but the shape and size have not changed the structural properties of the terrain. The different topographic structure features of the two neighborhood strategies provide ideas for the design of the algorithm. Based on the above conclusions, a hybrid algorithm of particle swarm optimization and variable neighborhood search is proposed under the framework of generalized particle swarm optimization (GPSO) model. The Logistic model proposed in this paper is used to select an efficient neighborhood combination strategy. The results show that the commutation-based random whole neighborhood and the inserted N5 neighborhood have better combination effect. The test results show that the hybrid algorithm is better than the 40 examples of single neighborhood search la series, and 38 of the 40 examples can obtain the optimal solution, which verifies the superiority of the proposed algorithm. In the end, the thesis summarizes the whole paper and looks forward to the study of job shop scheduling and fitness terrain.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TH186

【參考文獻(xiàn)】

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

1 孫元凱,劉民,吳澄;變鄰域結(jié)構(gòu)Tabu搜索算法及其在Job Shop調(diào)度問題上的應(yīng)用[J];電子學(xué)報;2001年05期

2 彭傳勇;高亮;邵新宇;周馳;;求解作業(yè)車間調(diào)度問題的廣義粒子群優(yōu)化算法[J];計(jì)算機(jī)集成制造系統(tǒng);2006年06期

3 潘全科;王文宏;朱劍英;趙保華;;基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J];計(jì)算機(jī)集成制造系統(tǒng);2007年02期

4 高海兵;周馳;高亮;;廣義粒子群優(yōu)化模型[J];計(jì)算機(jī)學(xué)報;2005年12期

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

1 張超勇;基于自然啟發(fā)式算法的作業(yè)車間調(diào)度問題理論與應(yīng)用研究[D];華中科技大學(xué);2007年

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

1 潘保林;基于適應(yīng)度地形的組合優(yōu)化與作業(yè)車間調(diào)度問題研究[D];華中科技大學(xué);2008年

2 薛倩;求解JOB-SHOP車間作業(yè)調(diào)度的混合算法研究[D];大連交通大學(xué);2009年

3 何鐵芳;基于改進(jìn)廣義粒子群優(yōu)化的開放式車間調(diào)度方法研究[D];華中科技大學(xué);2009年

本文編號：2105506