基于蚁群算法与竞选算法的作业车间调度求解及比较研究

发布时间：2018-12-15 03:56

【摘要】：制造过程的调度技术,将在很大程度上影响产品生产的周期、成本和效率。优化制造过程调度,可以有效地提高企业的生产管理水平和制造自动化水平,从而提高企业的竞争力。作业车间调度问题是生产调度中许多实际问题的简化模型,是制造类企业无法回避的一个关键且核心的问题。现行的各种调度方法在求解作业车间调度问题时,都存在各种各样的缺陷。因此,改进现有的调度方法或者寻找新的调度方法,始终具有重要的理论价值和实际意义。蚁群算法的搜索机制模拟蚂蚁觅食过程中的群体行为,适合于求解旅行商问题等组合优化问题,但应用于作业车间调度问题的研究不多,且优化效果不明显,也没有一般性规律可循。竞选算法搜索机制模拟竞选活动中对更高支持率的追求动机,目前主要应用于连续域内的各种函数优化问题。本文针对作业车间调度问题,对蚁群算法进行改进,设计了一种新的信息素更新方式；对竞选算法进行离散化设计,探索新的求解作业车间调度问题的调度方法,并对这两种算法进行比较。本文的主要研究结果如下： (1)本文综合分析了蚁群算法的特点及作业车间调度问题的特点,讨论了两种经典的改进蚁群算法—蚁群系统与最大最小蚂蚁系统—的算法思想及求解机制。在此基础上,提出了一种新的改进蚁群算法。为了验证该改进蚁群算法的有效性,将其应用于作业车间调度问题与柔性作业车间调度问题的求解。采用文献中的测试函数进行计算,并将计算结果与文献中的结果进行比较分析。结果表明,该改进蚁群算法大大提高了问题的求解效率及求解结果。 (2)介绍了竞选算法的基本思想、基本原理以及在连续优化领域内的应用研究。将竞选算法应用于求解作业车间生产调度问题,采用基于工序的表达法表示问题的解,采用基于关键路径的邻域搜索方法生成局部选民,这两者是竞选算法的离散化设计的核心技术。将离散化的竞选算法求解FT06算例以及LA系列标准调度函数,无论是计算时间,还是计算结果,离散的竞选算法都取得了较好的效果,表明了该改进算法的有效性及可行性。 (3)利用Matlab 7编程实现了上述两种算法的操作,构建了一个求解作业车间调度问题的工具包。 (4)分析了改进蚁群算法与改进竞选算法两种启发式优化算法在算法特性方面的异同点,并对这两种算法进行求解质量、算法时间复杂度和空间复杂度等方面的比较分析。
[Abstract]:The scheduling technology of manufacturing process will affect the production cycle, cost and efficiency to a great extent. Optimization of manufacturing process scheduling can effectively improve the level of production management and manufacturing automation, thereby improving the competitiveness of enterprises. Job shop scheduling problem is a simplified model of many practical problems in production scheduling. It is a key and core problem that manufacturing enterprises can not avoid. All kinds of current scheduling methods have various defects in solving job shop scheduling problems. Therefore, it is always of great theoretical and practical significance to improve the existing scheduling methods or to find new scheduling methods. The search mechanism of ant colony algorithm simulates colony behavior in ant foraging process, which is suitable for solving combinatorial optimization problems such as traveling salesman problem. However, there are few researches on job shop scheduling problem and the effect of optimization is not obvious. There are no general rules to follow. The search mechanism of election algorithm simulates the motivation for higher support in the campaign, which is mainly applied to various functional optimization problems in continuous domain. In this paper, a new pheromone updating method is designed for job shop scheduling problem by improving ant colony algorithm. The election algorithm is discretized and a new scheduling method for job shop scheduling problem is explored and compared. The main results of this paper are as follows: (1) the characteristics of ant colony algorithm and job shop scheduling problem are analyzed. Two classical improved ant colony algorithms, ant colony system and maximum and minimum ant system, are discussed in this paper. On this basis, a new improved ant colony algorithm is proposed. In order to verify the effectiveness of the improved ant colony algorithm, it is applied to the solution of job shop scheduling problem and flexible job shop scheduling problem. The test function in the literature is used to calculate, and the calculated results are compared with the results in the literature. The results show that the improved ant colony algorithm greatly improves the efficiency and the result of solving the problem. (2) the basic idea, basic principle and application research in the field of continuous optimization are introduced. The election algorithm is applied to solve the job shop production scheduling problem. The solution of the problem is represented by the expression method based on the process, and the local voters are generated by the neighborhood search method based on the critical path. These two are the core techniques of discrete design of campaign algorithms. The discrete election algorithm is used to solve the FT06 example and the LA series standard scheduling function. Both the computing time and the result of the discrete election algorithm are obtained. The results show that the improved algorithm is effective and feasible. (3) Matlab 7 is used to realize the operation of the above two algorithms, and a toolkit to solve the job shop scheduling problem is constructed. (4) the similarities and differences between the improved ant colony algorithm and the improved election algorithm are analyzed, and the quality, time complexity and space complexity of the two algorithms are compared and analyzed.
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186

【相似文献】