基于EDA智能優(yōu)化算法的復(fù)雜車間調(diào)度問題研究
發(fā)布時(shí)間：2018-08-04 13:07
【摘要】：生產(chǎn)制造系統(tǒng)中通常伴隨有規(guī)模大、強(qiáng)約束、非線性、多目標(biāo)、不確定、NP-hard等諸多復(fù)雜因素,因此針對智能優(yōu)化算法和生產(chǎn)調(diào)度理論的應(yīng)用與研究始終都是工業(yè)界與學(xué)術(shù)界的重要研究課題。流水線調(diào)度是一類非常典型且有廣泛工程背景的復(fù)雜組合優(yōu)化問題,其相關(guān)理論和算法的研究具有重要的科研價(jià)值與實(shí)際意義。分布估計(jì)算法借鑒機(jī)器學(xué)習(xí)中的統(tǒng)計(jì)學(xué)習(xí)進(jìn)化思想,有較強(qiáng)的全局引導(dǎo)性,已成為優(yōu)化領(lǐng)域的研究熱點(diǎn)。本文研究兩類典型的流水線生產(chǎn)調(diào)度問題,結(jié)合問題特性提出了有效的全局模型,并設(shè)計(jì)了高效的局部策略,提出的增強(qiáng)分布估計(jì)算法可為流水優(yōu)化調(diào)度提供理論與算法支持。全面綜述兩類復(fù)雜流水調(diào)度問題和分布估計(jì)算法研究進(jìn)展的基礎(chǔ)上,本文的研究工作主要獲得以下成果:(1)針對優(yōu)化指標(biāo)為最小化總完工時(shí)間的帶序相關(guān)設(shè)置時(shí)間與釋放時(shí)間的零等待流水線調(diào)度問題,提出了一種采用快速評價(jià)和基于問題性質(zhì)的Insert局部搜索的有效混合分布估計(jì)算法。通過典型算例的大量仿真結(jié)果和算法比較,驗(yàn)證了所提算法的有效性與魯棒性。(2)針對優(yōu)化指標(biāo)為最小化總體提前和滯后時(shí)間的帶序相關(guān)設(shè)置時(shí)間和釋放時(shí)間的零等待流水線調(diào)度問題,首次提出了一種有效的基于三維矩陣立方體的分布估計(jì)算法,能夠有效學(xué)習(xí)解空間內(nèi)優(yōu)秀解的序關(guān)系和構(gòu)造塊信息,引導(dǎo)全局搜索方向;并設(shè)計(jì)了基于快速掃描方法和兩種有效搜索策略的快速局部搜索方法,用于對已尋找到優(yōu)勢解區(qū)域進(jìn)行深度搜索。此外,還進(jìn)一步探討了關(guān)鍵參數(shù)和操作對算法性能的影響。通過典型測試問題的仿真結(jié)果與比較,驗(yàn)證了所提算法的有效性和魯棒性。(3)針對分布式兩階段裝配流水線調(diào)度問題,給出了其數(shù)學(xué)描述并設(shè)計(jì)了考慮問題特性的有效編碼與解碼方法。通過基于三維矩陣立方體的分布估計(jì)算法最小化其最大完工時(shí)間,設(shè)計(jì)了關(guān)鍵路徑搜索方法和變鄰域搜索并應(yīng)用于Insert和Interchange的局部搜索中,進(jìn)而加速引導(dǎo)進(jìn)化方向使其趨近于全局最優(yōu)區(qū)域。通過國際標(biāo)準(zhǔn)問題集的大量仿真測試和算法比較,驗(yàn)證了所提方法的有效性、高效性和魯棒性。
[Abstract]:Manufacturing systems are usually accompanied by large scale, strong constraints, nonlinear, multi-objective, uncertain NP-hard and many other complex factors. Therefore, the application and research of intelligent optimization algorithm and production scheduling theory is always an important research topic in industry and academia. Pipeline scheduling is a kind of complex combinatorial optimization problem with a very typical and extensive engineering background. The research of related theories and algorithms has important scientific research value and practical significance. The distribution estimation algorithm, which uses the evolutionary thought of statistical learning in machine learning for reference, has a strong global guidance and has become a hot research topic in the field of optimization. In this paper, two kinds of typical pipeline production scheduling problems are studied, and an effective global model is proposed based on the characteristics of the problem, and an efficient local strategy is designed. The proposed augmented distribution estimation algorithm can provide theoretical and algorithmic support for pipeline optimal scheduling. Based on a comprehensive review of the research progress of two kinds of complex pipeline scheduling problems and distribution estimation algorithms, The main achievements of this paper are as follows: (1) for the zero wait pipeline scheduling problem with order dependent setup time and release time, the optimization index is to minimize the total completion time. An efficient mixed distribution estimation algorithm based on fast evaluation and Insert local search based on problem properties is proposed. A large number of simulation results and algorithms are compared with typical examples. The effectiveness and robustness of the proposed algorithm are verified. (2) the zero-wait pipeline scheduling problem with sequence dependent setup time and release time is optimized to minimize the overall advance and delay time. For the first time, an effective distribution estimation algorithm based on 3D matrix cubes is proposed, which can effectively learn the order relation of excellent solutions in solution space and the information of construction blocks, and guide the global search direction. A fast local search method based on the fast scanning method and two effective search strategies is designed to search the region where the dominant solution has been found. In addition, the effects of key parameters and operations on the performance of the algorithm are also discussed. Simulation results of typical test problems show that the proposed algorithm is effective and robust. (3) for the distributed two-stage assembly pipeline scheduling problem, The mathematical description is given and an effective encoding and decoding method considering the characteristics of the problem is designed. The distribution estimation algorithm based on 3D matrix cube is used to minimize the maximum completion time. A critical path search method and variable neighborhood search are designed and applied to the local search of Insert and Interchange. Furthermore, it can accelerate the direction of evolution and make it approach the global optimal region. The effectiveness, efficiency and robustness of the proposed method are verified by a large number of simulation tests and algorithm comparisons of the international standard problem sets.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;TB497
本文編號：2163977
[Abstract]:Manufacturing systems are usually accompanied by large scale, strong constraints, nonlinear, multi-objective, uncertain NP-hard and many other complex factors. Therefore, the application and research of intelligent optimization algorithm and production scheduling theory is always an important research topic in industry and academia. Pipeline scheduling is a kind of complex combinatorial optimization problem with a very typical and extensive engineering background. The research of related theories and algorithms has important scientific research value and practical significance. The distribution estimation algorithm, which uses the evolutionary thought of statistical learning in machine learning for reference, has a strong global guidance and has become a hot research topic in the field of optimization. In this paper, two kinds of typical pipeline production scheduling problems are studied, and an effective global model is proposed based on the characteristics of the problem, and an efficient local strategy is designed. The proposed augmented distribution estimation algorithm can provide theoretical and algorithmic support for pipeline optimal scheduling. Based on a comprehensive review of the research progress of two kinds of complex pipeline scheduling problems and distribution estimation algorithms, The main achievements of this paper are as follows: (1) for the zero wait pipeline scheduling problem with order dependent setup time and release time, the optimization index is to minimize the total completion time. An efficient mixed distribution estimation algorithm based on fast evaluation and Insert local search based on problem properties is proposed. A large number of simulation results and algorithms are compared with typical examples. The effectiveness and robustness of the proposed algorithm are verified. (2) the zero-wait pipeline scheduling problem with sequence dependent setup time and release time is optimized to minimize the overall advance and delay time. For the first time, an effective distribution estimation algorithm based on 3D matrix cubes is proposed, which can effectively learn the order relation of excellent solutions in solution space and the information of construction blocks, and guide the global search direction. A fast local search method based on the fast scanning method and two effective search strategies is designed to search the region where the dominant solution has been found. In addition, the effects of key parameters and operations on the performance of the algorithm are also discussed. Simulation results of typical test problems show that the proposed algorithm is effective and robust. (3) for the distributed two-stage assembly pipeline scheduling problem, The mathematical description is given and an effective encoding and decoding method considering the characteristics of the problem is designed. The distribution estimation algorithm based on 3D matrix cube is used to minimize the maximum completion time. A critical path search method and variable neighborhood search are designed and applied to the local search of Insert and Interchange. Furthermore, it can accelerate the direction of evolution and make it approach the global optimal region. The effectiveness, efficiency and robustness of the proposed method are verified by a large number of simulation tests and algorithm comparisons of the international standard problem sets.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;TB497
【參考文獻(xiàn)】
相關(guān)期刊論文 前6條
1 周樹德;孫增圻;;分布估計(jì)算法綜述[J];自動(dòng)化學(xué)報(bào);2007年02期
2 程玉虎;王雪松;郝名林;;一種多樣性保持的分布估計(jì)算法[J];電子學(xué)報(bào);2010年03期
3 譚立湘;郭立;;基于全面學(xué)習(xí)的量子分布估計(jì)算法[J];模式識別與人工智能;2010年03期
4 王圣堯;王凌;方晨;許燁;;分布估計(jì)算法研究進(jìn)展[J];控制與決策;2012年07期
5 王凌;鄧瑾;王圣堯;;分布式車間調(diào)度優(yōu)化算法研究綜述[J];控制與決策;2016年01期
6 Ling Wang;Shengyao Wang;Xiaolong Zheng;;A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times[J];IEEE/CAA Journal of Automatica Sinica;2016年03期
，本文編號：2163977
本文鏈接：http://www.wukwdryxk.cn/guanlilunwen/gongchengguanli/2163977.html
最近更新
教材專著
