蚁群鱼群混合算法在差异工件批调度中的应用

发布时间：2018-05-13 21:30

本文选题：批调度 + 蚁群算法　；参考：《中国科学技术大学》2017年硕士论文

【摘要】：在现实的生产生活中,无论是机器加工、零件制造,还是货物装运、航天运输,都需要解决调度问题。调度问题不仅是一种组合优化问题,更有着广泛的应用背景,它在提高全社会资源利用效率、劳动生产率和降低生产成本方面起到了极其积极巨大的作用,并且有着非常丰富的研究成果。批调度问题是对经典调度问题的扩展,主要是起源于半导体生产过程中的一类新型现代调度问题。批调度问题具有非常重要的理论和经济研究价值。本论文研究的批调度问题是NP-难问题,而简单高效的求解算法设计是批调度研究的重点方向。文中主要用到的算法为蚁群算法和鱼群算法。在简单介绍蚁群算法和鱼群算法的思想和应用后,还根据算法特性以及视野限制的问题,提出了一种改进的鱼群算法,通过视野的动态变化,改进算法前期搜索宽度和后期收敛速度,实现算法效率的提高,并且通过案例结果分析,改进的鱼群算法比传统鱼群算法更加高效。本文还根据批调度问题特性,结合蚁群算法和鱼群算法之间的优缺点,提出了两种混合算法,混合算法通过鱼群算法拥挤度因子的结合,避免蚁群算法在早期陷入局部极值,从而导致算法早熟的缺点,使算法具有全局寻优能力,能更好的找到全局极值。文中主要解决的问题是差异工件单机批调度问题,该问题中工件尺寸不尽相同,并且只有一台加工机器。针对具体问题算法参数需要重新设置,文中对蚁群算法中信息素定义、启发式信息和信息素初始化作出相应改进,并且对鱼群算法也有相应的调整。为保证实验的说服力和有效性,本文根据实验的数量的多少、工件加工的尺寸大小和工件加工时间的长短,进行了分类的实验。为了直观全面地对比实验结果的好坏,我们应用了批的利用率和负载率的概念。批的利用率侧面反应了在批加工时间内,工件加工对机器容量的利用程度;批的负载率体现总体加工时间中浪费程度。从实验结果看,在算法寻优的过程中,蚁群算法的性能要优于鱼群算法,但是蚁群算法本身的早熟性,导致寻优结果局部最优。但如果将蚁群算法和鱼群算法相结合,利用鱼群算法中的拥挤度因子,并与蚁群算法相结合,可以有效地避免早熟,并且对于寻找最优解、减少寻优时间有着一定的帮助。通过第一种混合算法和第二种混合算法的比较,第二种混合算法对于工件数量较小、迭代次数较少的问题有较高效率。而第一种混合算法对于工件数量较多,迭代次数较多的算法有较高的性能。
[Abstract]:In the actual production and life, the scheduling problem needs to be solved whether machine processing, parts manufacturing, cargo shipment and space transportation. The scheduling problem is not only a combination optimization problem, but also a wide application background. It plays an extremely important role in improving the utilization efficiency of the whole society, labor productivity and reducing the cost of production. The batch scheduling problem is a new type of modern scheduling problem originating in the process of semiconductor production. The batch scheduling problem has very important theoretical and economic research value. The batch scheduling problem in this paper is a NP- difficult problem. And simple and efficient algorithm design is the key direction of batch scheduling research. The main algorithms used in this paper are ant colony algorithm and fish swarm algorithm. After simply introducing the idea and application of ant colony algorithm and fish swarm algorithm, an improved fish swarm algorithm is proposed based on the characteristics of the algorithm and the limit of field of vision. State changes, improved algorithm early search width and later convergence speed, improve the efficiency of the algorithm, and through the analysis of the case results, the improved fish swarm algorithm is more efficient than the traditional fish swarm algorithm. Based on the characteristics of the batch scheduling problem, combined with the advantages and disadvantages of ant colony algorithm and fish swarm algorithm, two hybrid algorithms are proposed. By combining the crowding factor of the fish swarm algorithm, the algorithm avoids the early fall of the ant colony algorithm into the local extremum, which leads to the premature weakness of the algorithm, and makes the algorithm have the global optimization ability, and can better find the global extremum. The main problem in this paper is the problem of the single machine batch scheduling problem of the difference workpieces, and the size of the workpiece is not the same in the problem. There is only one machine. In order to ensure the persuasiveness and effectiveness of the fish swarm algorithm, the pheromone definition, the heuristic information and the pheromone initialization of the ant colony algorithm are improved in this paper. The size of the processing and the length of the working time of the workpiece are classified. In order to compare the results of the experiment directly and comprehensively, we apply the concept of the utilization ratio and the load rate of the batch. The utilization ratio of the batch reacts to the utilization degree of the machine capacity during the batch processing time; the load rate of the batch shows the total. From the experimental results, in the process of optimizing the algorithm, the performance of the ant colony algorithm is better than the fish algorithm, but the early maturity of the ant colony algorithm itself leads to the local optimization of the optimization results. But if the ant colony algorithm is combined with the fish algorithm, the crowding factor in the fish swarm algorithm is used and the ant colony algorithm is used. Combined, it can effectively avoid precocity and help to find the optimal solution and reduce the optimization time. Through the comparison between the first hybrid algorithm and the second hybrid algorithms, the second hybrid algorithm is more efficient for smaller number of jobs and less iterative times. The first hybrid algorithm is more effective for the number of jobs. Many algorithms with more iterations have higher performance.

【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】