發(fā)布時(shí)間：2018-04-10 16:38

  本文選題：人工蜂群算法 + 復(fù)雜度��； 參考：《北京交通大學(xué)》2014年碩士論文

【摘要】：作業(yè)車間調(diào)度(Job-Shop)問題是求解滿足順序約束要求和任務(wù)配置的資源分配問題,有效地求解該問題對于提供生產(chǎn)效率、降低生產(chǎn)成本有著極其重要的作用,因此受到廣泛的關(guān)注。但作業(yè)車間調(diào)度問題是非常典型的NP-hard問題,迄今為止仍未找到可以精確求得最優(yōu)解的多項(xiàng)式時(shí)間算法。人工蜂群算法(ABC)是模擬蜜蜂群采蜜過程進(jìn)行隨機(jī)優(yōu)化的一種新型群體智能算法,對于解決復(fù)雜的優(yōu)化問題有良好的效果。該算法具有設(shè)置參數(shù)少、易于實(shí)現(xiàn)和魯棒性強(qiáng)等特點(diǎn)。研究ABC算法并將之用于求解作業(yè)車間調(diào)度問題將具有重要的理論意義與實(shí)用價(jià)值。 論文首先介紹了ABC算法的基本原理以及研究現(xiàn)狀,在此基礎(chǔ)上主要完成了以下創(chuàng)新性工作： a)首次對比分析了ABC、GA、ACO和PSO四種算法的時(shí)間和空間復(fù)雜度、、收斂速度及求解精度,指出基本ABC算法與其它三種算法相比盡管在解決優(yōu)化問題上具有優(yōu)勢,但仍不適合求解作業(yè)車間調(diào)度問題。 b)根據(jù)經(jīng)典的Job-Shop問題數(shù)學(xué)模型的描述方法,結(jié)合Job-Shop問題具有排列優(yōu)化和組合優(yōu)化的特點(diǎn),提出了一種基于排列組合的Job-Shop數(shù)學(xué)模型描述方法； c)根據(jù)所提出的模型描述方法,對基本ABC算法從初始化、鄰域搜索、偵查蜂搜索蜜源和適應(yīng)度計(jì)算等方面進(jìn)行了改進(jìn),使之適合求解Job-Shop問題。最后通過典型的Job-Shop問題實(shí)驗(yàn)仿真驗(yàn)證了改進(jìn)后的ABC算法對于求解作業(yè)車間調(diào)度問題的有效性。
[Abstract]:Job-Shop-Job-Shopproblem is a resource allocation problem that meets the requirements of order constraints and task configurations. It is very important to solve the problem effectively for providing production efficiency and reducing production cost, so it has been paid more and more attention.But job shop scheduling problem is a typical NP-hard problem, so far, no polynomial time algorithm can be found to find the optimal solution.Artificial bee colony algorithm (ABC) is a new type of swarm intelligence algorithm which simulates the honeybee honey gathering process and has a good effect on solving the complex optimization problem.The algorithm has the advantages of less setting parameters, easy to implement and strong robustness.It is of great theoretical significance and practical value to study ABC algorithm and apply it to solving job shop scheduling problems.Firstly, this paper introduces the basic principle and research status of ABC algorithm. On this basis, it mainly completes the following innovative work:A) for the first time, the time and space complexity, convergence speed and solution accuracy of the four algorithms are compared and analyzed. It is pointed out that the basic ABC algorithm is superior to the other three algorithms in solving optimization problems.However, it is still not suitable for solving job shop scheduling problems.B) according to the classical description method of mathematical model of Job-Shop problem and combining the characteristics of Job-Shop problem with arrangement optimization and combinatorial optimization, a description method of Job-Shop mathematical model based on permutation and combination is proposed.C) based on the proposed model description method, the basic ABC algorithm is improved in initialization, neighborhood search, bee detection honey source and fitness calculation to make it suitable for solving Job-Shop problem.Finally, the effectiveness of the improved ABC algorithm in solving job shop scheduling problem is verified by the simulation of typical Job-Shop problem.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TB497;TP18

【參考文獻(xiàn)】

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

1 胡中華;趙敏;;基于人工蜂群算法的TSP仿真[J];北京理工大學(xué)學(xué)報(bào);2009年11期

2 胡中華;趙敏;;基于人工蜂群算法的無人機(jī)航跡規(guī)劃研究[J];傳感器與微系統(tǒng);2010年03期

3 胡中華;趙敏;;基于人工蜂群算法的機(jī)器人路徑規(guī)劃[J];電焊機(jī);2009年04期

4 柳寅;馬良;黃鈺;;模糊人工蜂群算法的置換流水車間調(diào)度問題求解[J];工業(yè)工程與管理;2013年04期

5 宋存利;時(shí)維國;;求解柔性Job-shop調(diào)度問題的混合粒子群算法[J];大連交通大學(xué)學(xué)報(bào);2013年06期

6 丁海軍;馮慶嫻;;基于boltzmann選擇策略的人工蜂群算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年31期

7 暴勵(lì);曾建潮;;自適應(yīng)搜索空間的混沌蜂群算法[J];計(jì)算機(jī)應(yīng)用研究;2010年04期

8 王凌,鄭大鐘;基于遺傳算法的Job Shop調(diào)度研究進(jìn)展[J];控制與決策;2001年S1期

9 王凌;周剛;許燁;王圣堯;;求解不相關(guān)并行機(jī)混合流水線調(diào)度問題的人工蜂群算法[J];控制理論與應(yīng)用;2012年12期

10 薛宏全;魏生民;張鵬;楊琳;;基于多種群蟻群算法的柔性作業(yè)車間調(diào)度研究[J];計(jì)算機(jī)工程與應(yīng)用;2013年24期

，

本文編號(hào)：1732088