求解作业车间调度问题的离散差分进化算法研究

发布时间：2018-03-16 01:36

本文选题：车间调度问题　切入点：差分进化算法　出处：《沈阳工业大学》2016年硕士论文　论文类型：学位论文

【摘要】：调度是一个决策的过程,它在制造和生产系统中扮演着重要的角色。作业车间调度问题是一类非常重要的生产调度问题,具有广泛的实际应用背景。然而车间调度是一类典型的组合优化问题,具有NP难特征。尽管迄今人们提出很多种调度算法,然而由于调度问题本身的复杂性以及应用环境的日趋复杂,有必要对车间调度问题进行进一步研究。差分进化算法属于群体智能优化算法,进行并行、随机的搜索操作。其在对大规模问题进行优化时,具有收敛速度快、准确性高的优点。虽然差分进化算法具有高效特性,但因本身具有连续特性,当应用于求解调度问题时,需要对其进行离散化后才可以应用。为此本文针对车间调度的特点,对差分进化算法进行深入研究,并分别对典型作业车间调度问题以及分布式车间调度问题进行具体研究。针对作业调度问题,本文结合国内外研究现状,深入分析作业车间调度问题的结构特点和算法的基本原理对算法做了两方面的更改。首先在变异操作中,采用了自适应变异因子。自适应变异因子可以根据迭代次数的增加,动态调整算法的性能,在迭代初期保证种群的多样性,在迭代后期避免算法对最优解的盲目更改。其次根据交叉操作基本原理,通过更改提供父辈的方式,对试验个体每个不可行位进行重新选择,使交叉操作可以直接产生可行调度解。对于分布式车间调度,在深入研究的基础上,增加对工厂的选择操作。为了验证所提出算法的可行性,将本文所提出算法记为DE1。将交叉操作产生不可行解时只进行随机生成可行解的离散差分进化算法记为DE2。本文以VC++6.0和MATLAB综合作为仿真环境。首先利用MATLAB丰富的库函数对差分进化算法进行实现,对于车间调度问题生成甘特图部分,由于运算量十分庞大,本文运用MEX文件调用C语言,利用C语言高效的运算能力进行求解,缩短算法的仿真时间。利用DE1、DE2算法分别对FT06、FT10、LA01、LA06、LA11和分布式车间调度问题实例进行仿真。结果表明所提出离散差分进化算法应用到作业调度问题的可行性和高效性。
[Abstract]:Scheduling is a decision-making process, it plays an important role in manufacturing and production systems. Job shop scheduling problem is a very important production scheduling problem. However, job shop scheduling is a typical combinatorial optimization problem with NP-hard characteristics. Although so far, many scheduling algorithms have been proposed. However, due to the complexity of the scheduling problem itself and the increasing complexity of the application environment, it is necessary to further study the job shop scheduling problem. Random search operation. It has the advantages of fast convergence and high accuracy in optimizing large-scale problems. Although the differential evolution algorithm has the characteristics of high efficiency, but because of its own continuous characteristics, when it is applied to solve scheduling problems, It needs to be discretized before it can be applied. In this paper, according to the characteristics of job shop scheduling, the differential evolution algorithm is deeply studied. The typical job shop scheduling problem and the distributed job shop scheduling problem are studied respectively. The structural characteristics of the job shop scheduling problem and the basic principle of the algorithm are analyzed in depth. Firstly, the adaptive mutation factor is adopted in the mutation operation. The adaptive variation factor can be increased according to the number of iterations. By dynamically adjusting the performance of the algorithm, the diversity of the population is guaranteed at the early stage of iteration, and the blind change of the optimal solution is avoided at the later stage of iteration. Secondly, according to the basic principle of crossover operation, the method of providing the parent through the change is proposed. Each unfeasible bit is re-selected so that the crossover operation can directly produce feasible scheduling solutions. For distributed job shop scheduling, based on the in-depth study, To verify the feasibility of the proposed algorithm, The algorithm proposed in this paper is described as DE1.The discrete differential evolutionary algorithm (DDA), which only generates the feasible solution at random when the cross operation produces the infeasible solution, is denoted as DE2.In this paper, VC 6.0 and MATLAB synthesis are used as the simulation environment. Firstly, the rich library of MATLAB is used as the simulation environment. Function to realize the differential evolution algorithm, For the Gantt graph part of the job shop scheduling problem, because of the huge amount of computation, this paper uses MEX file to call C language, and makes use of C language's efficient computing ability to solve the problem. The simulation time of the algorithm is shortened. The examples of FT06X / FT10L / LA06 / LA11 and distributed job shop scheduling problem are simulated using DE1DE2 algorithm, respectively. The results show that the proposed discrete differential evolution algorithm is feasible and efficient in job scheduling problems.
【学位授予单位】：沈阳工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TB497

【相似文献】