人工蜂群算法及其在调度问题中的应用研究

发布时间：2018-04-10 16:38

本文选题：人工蜂群算法 + 复杂度　；参考：《北京交通大学》2014年硕士论文

【摘要】：作业车间调度(Job-Shop)问题是求解满足顺序约束要求和任务配置的资源分配问题,有效地求解该问题对于提供生产效率、降低生产成本有着极其重要的作用,因此受到广泛的关注。但作业车间调度问题是非常典型的NP-hard问题,迄今为止仍未找到可以精确求得最优解的多项式时间算法。人工蜂群算法(ABC)是模拟蜜蜂群采蜜过程进行随机优化的一种新型群体智能算法,对于解决复杂的优化问题有良好的效果。该算法具有设置参数少、易于实现和鲁棒性强等特点。研究ABC算法并将之用于求解作业车间调度问题将具有重要的理论意义与实用价值。论文首先介绍了ABC算法的基本原理以及研究现状,在此基础上主要完成了以下创新性工作： a)首次对比分析了ABC、GA、ACO和PSO四种算法的时间和空间复杂度、、收敛速度及求解精度,指出基本ABC算法与其它三种算法相比尽管在解决优化问题上具有优势,但仍不适合求解作业车间调度问题。 b)根据经典的Job-Shop问题数学模型的描述方法,结合Job-Shop问题具有排列优化和组合优化的特点,提出了一种基于排列组合的Job-Shop数学模型描述方法； c)根据所提出的模型描述方法,对基本ABC算法从初始化、邻域搜索、侦查蜂搜索蜜源和适应度计算等方面进行了改进,使之适合求解Job-Shop问题。最后通过典型的Job-Shop问题实验仿真验证了改进后的ABC算法对于求解作业车间调度问题的有效性。
[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.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497;TP18

【参考文献】