SAGA算法在差异工件平行机批调度问题中的应用研究

发布时间：2018-05-20 01:26

本文选题：调度 + 差异工件　；参考：《中国科学技术大学》2011年硕士论文

【摘要】：调度问题是组合优化领域中一类重要的问题,它广泛地应用在制造业、现代物流和网络通信等领域,本文主要研究的是生产调度问题,有效的调度能够提高机器利用率、降低成本、增加利润和提升客户满意度。本文的研究目标是最小化差异工件平行机批调度问题的制造时间跨度Cmax,在调度问题的研究中,Cmax经常被用来衡量调度的性能,与差异工件单机批调度问题相比,差异工件平行机批调度问题更接近现实生产活动,而且目前关于该问题的研究仍然较少。本文首先简述了调度问题的概念、研究意义、分类和参数表示、经典调度与现代调度的区别以及差异工件批调度问题的概念。同时,我们也简单介绍了组合优化问题的概念与计算复杂性的相关基础知识。由于差异工件批调度问题是一类典型的NP-hard问题,所以解决该类问题的关键在于寻求有效的优化算法。目前,求解差异工件批调度问题的主要方法有两种:(1)数学规划方法;(2)启发式方法。前者虽然可以求得问题的最优解,但是只适用在小规模问题中,后者虽然在大多数情况下不能得到最优解,但是它能有效地解决大规模问题,在一定时间内给出一个在可以接受范围内的近似最优解,具有更强的实际可操作性。本文介绍了目前求解差异工件批调度问题的主要的数学规划方法和启发式方法及其研究情况。根据问题的特性,本文设计了一种面向差异工件平行机批调度问题的模拟退火遗传算法(Simulated Annealing Genetic Algorithm,SAGA)。SAGA算法集合了模拟退火算法(Simulated Annealing,SA)和遗传算法(Genetic Algorithm,GA)在局部搜索与全局搜索能力方面的优势,并改进了遗传算法的交叉方式和适应函数的标定方式。仿真实验表明,SAGA算法的性能优于现有文献中的两个经典启发式规则FFLPT和BFLPT以及GA算法。最后,我们总结了本文的主要工作和创新点,并提出了未来可以继续进行研究的方向。
[Abstract]:Scheduling problem is an important problem in the field of combinatorial optimization. It is widely used in manufacturing industry, modern logistics and network communication. Reduce costs, increase profits and improve customer satisfaction. The goal of this paper is to minimize the manufacturing time span of the different workpiece parallel machine batch scheduling problem (Cmax). In the research of the scheduling problem, Cmax is often used to measure the scheduling performance, compared with the differential workpiece single batch scheduling problem. The problem of batch scheduling of parallel machines is closer to real production activities, and the research on this problem is still less. In this paper, the concept of scheduling problem, its significance, classification and parameter representation, the difference between classical scheduling and modern scheduling, and the concept of different job batch scheduling problem are introduced in this paper. At the same time, we also briefly introduce the concept of combinatorial optimization problems and the basic knowledge of computational complexity. Because the differential job batch scheduling problem is a typical NP-hard problem, the key to solve this problem is to find an effective optimization algorithm. At present, there are two main methods for solving batch scheduling problem of different jobs: 1) mathematical programming method and 2) heuristic method. Although the former can obtain the optimal solution of the problem, it is only suitable for the small scale problem. Although the latter can not obtain the optimal solution in most cases, it can effectively solve the large-scale problem. An approximate optimal solution within an acceptable range is given in a certain time, which is more practical and operable. In this paper, the main mathematical programming methods and heuristic methods for solving batch scheduling problems with different jobs and their research situation are introduced. Depending on the nature of the problem, In this paper, a simulated Annealing Genetic algorithm named simulated Annealing Genetic algorithm is designed for batch scheduling of different jobs. The algorithm gathers the advantages of simulated annealing algorithm (SA) and genetic algorithm (GA) in local search and global search. The crossover method of genetic algorithm and the calibration method of adaptive function are improved. The simulation results show that the performance of the algorithm is better than the two classical heuristic rules FFLPT, BFLPT and GA. Finally, we summarize the main work and innovation of this paper, and propose the future research direction.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186;TP18

【参考文献】