本文選題：差分進(jìn)化算法　切入點(diǎn)：分布估計(jì)算法　出處：《昆明理工大學(xué)》2014年碩士論文　論文類(lèi)型：學(xué)位論文

【摘要】：車(chē)間調(diào)度問(wèn)題通常存在非線(xiàn)性、強(qiáng)約束、多目標(biāo)、不確定等復(fù)雜性,而且規(guī)模龐大、建模困難。開(kāi)發(fā)適合于復(fù)雜生產(chǎn)車(chē)間調(diào)度問(wèn)題的智能優(yōu)化算法,已經(jīng)成為生產(chǎn)調(diào)度領(lǐng)域的研究熱點(diǎn)。差分進(jìn)化算法(DE)是一種新興的群智能進(jìn)化算法,可用于求解復(fù)雜的優(yōu)化問(wèn)題。分布估計(jì)算法(EDA)是一種基于優(yōu)勢(shì)個(gè)體概率模型的進(jìn)化算法,可從較為宏觀的角度實(shí)現(xiàn)對(duì)問(wèn)題解空間的搜索。 本文將DE和EDA應(yīng)用于復(fù)雜車(chē)間調(diào)度問(wèn)題上。主要工作如下： (1)針對(duì)實(shí)際生產(chǎn)環(huán)境中廣泛存在的帶有序相關(guān)設(shè)置時(shí)間(SDSTs)和工件釋放時(shí)間(RDs)的零等待流水線(xiàn)調(diào)度問(wèn)題(NFSSP),設(shè)計(jì)了一種用于最小化總延遲時(shí)間的混合差分進(jìn)化算法(HDE)。 (2)為了有效求解最大完工時(shí)間(makespan)指標(biāo)下的m臺(tái)機(jī)器可重入置換流水線(xiàn)調(diào)度問(wèn)題(MRPFSSP),提出了三種基于EDA的算法。首先,提出了一種基于Insert的變異方法和Interchange的局部搜索策略的混合EDA算法(HEDA);其次,提出了一種能夠自適應(yīng)調(diào)整學(xué)習(xí)速率的混合EDA算法(SHEDA), SHEDA有效融合了基于關(guān)鍵路徑和塊結(jié)構(gòu)的局部搜索策略；最后,在對(duì)MRPFSSP的問(wèn)題結(jié)構(gòu)性質(zhì)進(jìn)行深入研究的基礎(chǔ)上,提出了一種基于Copula理論和關(guān)鍵路徑局部搜索策略的混合分布估計(jì)算法(CHEDA)。 (3)針對(duì)單目標(biāo)和多目標(biāo)下的三類(lèi)復(fù)雜并行機(jī)調(diào)度問(wèn)題(PMSP),設(shè)計(jì)了相應(yīng)的基于EDA的算法進(jìn)行求解。首先,提出了一種求解并行多機(jī)間歇調(diào)度問(wèn)題的自適應(yīng)EDA算法(AEDA),優(yōu)化目標(biāo)為makespan;其次,提出了一種改進(jìn)EDA算法(NED A),用于求解makespan指標(biāo)下的帶工件加工約束和序相關(guān)設(shè)置時(shí)間的異構(gòu)并行機(jī)調(diào)度問(wèn)題(HPMSP_JPCSST);第三,提出了一種遺傳-分布估計(jì)算法(GA-EDA),用于求解部分產(chǎn)品需多工序加工,同時(shí)不同產(chǎn)品間帶序相關(guān)設(shè)置時(shí)間的異構(gòu)并行機(jī)調(diào)度問(wèn)題(HPMSP_MOSST),優(yōu)化目標(biāo)為makespan;最后,提出了一種基于Copula理論的多目標(biāo)分布估計(jì)算法(CMEDA),由于求解nakespan和總轉(zhuǎn)換費(fèi)用下的多目標(biāo)HPMSP MOSST。 仿真實(shí)驗(yàn)和算法比較對(duì)所提算法的有效性和魯棒性進(jìn)行了驗(yàn)證。
[Abstract]:Shop scheduling problem is usually nonlinear, strong constraint, multi-objective, uncertainty and complexity, large scale, difficult to model. Intelligent optimization algorithm is developed for complex production scheduling, production scheduling has become a hot research field. The differential evolution algorithm (DE) is a new kind of swarm intelligent algorithm that can be used to solve complex optimization problems. The estimation of distribution algorithm (EDA) is an evolutionary algorithm based on probabilistic model of individual advantage, can realize to search the solution space from a macro perspective.
In this paper, DE and EDA are applied to the problem of complex shop scheduling. The main work is as follows:
(1) aiming at the widely occurring zero wait pipeline scheduling problem (NFSSP) with real time set time (SDSTs) and job release time (RDs) in real production environment, a hybrid differential evolution algorithm (HDE) for minimizing total delay time is designed.
(2) in order to solve the problem of the maximum completion time (makespan) re entrant permutation flow shop scheduling index under m machine (MRPFSSP), put forward three kinds of algorithm based on EDA. Firstly, we propose a hybrid EDA algorithm with local search strategy variation method and Interchange based on Insert (HEDA); second and put forward a hybrid EDA algorithm with adaptive learning rate (SHEDA), SHEDA effective integration of the local search strategy based on the critical path and block structure; finally, based on an in-depth study of the problems on the structural properties of MRPFSSP, proposed a theory based on critical path and Copula hybrid local search strategy estimation of distribution algorithm (CHEDA).
(3) for the three types of single and multi objectives under the complicated parallel machine scheduling problem (PMSP), designed the EDA based algorithm is used to solve the problem. Firstly, we propose the adaptive EDA algorithm for multi machine batch scheduling for solving the problem of parallel (AEDA), the optimization goal is makespan; secondly, put forward a an improved EDA algorithm (NED A), is used for machine scheduling for makespan index with workpiece processing constraints and sequence dependent setup time of heterogeneous parallel problem (HPMSP_JPCSST); third, proposed a genetic - Estimation of distribution algorithm (GA-EDA), for solving some products need processing, machine scheduling and different products with sequence dependent setup time of heterogeneous parallel problem (HPMSP_MOSST), the optimization goal is makespan; finally, this paper puts forward an algorithm of multi-objective estimation of distribution based on the theory of Copula (CMEDA), the multi objective HPMS to solve nakespan and total conversion cost down P MOSST.
The effectiveness and robustness of the proposed algorithm are verified by simulation experiment and algorithm comparison.

【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類(lèi)號(hào)】：TB497;TP18

【參考文獻(xiàn)】

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

1 鐘偉才,劉靜,劉芳,焦李成;建立在一般結(jié)構(gòu)Gauss網(wǎng)絡(luò)上的分布估計(jì)算法[J];電子與信息學(xué)報(bào);2005年03期

2 趙小強(qiáng),榮岡;流程工業(yè)生產(chǎn)調(diào)度問(wèn)題綜述[J];化工自動(dòng)化及儀表;2004年06期

3 金鋒;宋士吉;楊建華;吳澄;;染整車(chē)間染缸優(yōu)化調(diào)度算法研究[J];計(jì)算機(jī)集成制造系統(tǒng);2008年03期

4 潘全科;王凌;高亮;桑紅燕;;基于差分進(jìn)化與塊結(jié)構(gòu)鄰域的作業(yè)車(chē)間調(diào)度優(yōu)化[J];機(jī)械工程學(xué)報(bào);2010年22期

5 錢(qián)斌;王凌;黃德先;江永亨;王雄;;動(dòng)態(tài)零等待流水線(xiàn)調(diào)度問(wèn)題的滾動(dòng)策略及優(yōu)化算法[J];控制與決策;2009年04期

6 王凌;王圣堯;方晨;;一種求解多維背包問(wèn)題的混合分布估計(jì)算法[J];控制與決策;2011年08期

7 王圣堯;王凌;方晨;許燁;;分布估計(jì)算法研究進(jìn)展[J];控制與決策;2012年07期

8 周樹(shù)德;孫增圻;;分布估計(jì)算法綜述[J];自動(dòng)化學(xué)報(bào);2007年02期

9 王麗芳;曾建潮;洪毅;;利用Copula函數(shù)估計(jì)概率模型并采樣的分布估計(jì)算法[J];控制與決策;2011年09期

10 王圣堯;王凌;許燁;;求解相同并行機(jī)混合流水線(xiàn)車(chē)間調(diào)度問(wèn)題的分布估計(jì)算法[J];計(jì)算機(jī)集成制造系統(tǒng);2013年06期

，

本文編號(hào)：1623455