基于DDE_VND算法的同等并行机调度问题的研究

发布时间：2018-03-20 21:08

本文选题：同等并行机调度　切入点：离散差分进化算法　出处：《华东理工大学》2012年硕士论文　论文类型：学位论文

【摘要】：生产调度的研究在过去几十年中发展迅速,人们对调度问题的模型和方法都做了大量的研究工作。由于许多实际调度问题属于NP完全问题,经典的调度理论和方法解决实际调度问题仍然面临各种难题。智能优化调度方法是近年来兴起的解决调度问题简单有效的方法,这类方法在不需要复杂数学模型的情况下即可获得较为满意的调度方案,是解决实际调度的最有效的途径之一本文研究了同等并行机调度问题,首先针对以制造期为目标的并行机调度模型,在离散差分进化算法(DDE)中融入变邻域下降(VND)的局部搜索策略,提出了DDE_VND算法。由于此算法融合了DDE和VND的优点,因此提高了DDE算法的搜索性能和效率,通过对DDE_VND算法和DDE算法的测试,表明了VND的有效性。在仿真实验中,采用标准算例,在相同运行条件下将DDE VND算法与DDE算法和遗传算法进行比较,实验结果表明了DDE_VND算法的效果更为显著。另外针对以总拖期为目标的同等并行机调度问题,本文对DDE_VND算法做了进一步改进,在DDE_VND算法中加入了一种改进的交货期规则(MDD)用于种群的初始化阶段,得到了改进后的MDDE_VND算法。并通过几个算例的验证和比较说明了此规则的有效性。仿真实验中采用标准算例,在同等运行条件下将MDDE_VND算法与DDE和克隆选择粒子群(CSPSO)算法进行了比较,达优率以及进化收敛曲线均体现了MDDE_VND算法的明显优势。并且利用统计学的方差分析(ANOVA)方法对算法的参数设置进行了讨论,选取了较好的一组参数值用于仿真实验。
[Abstract]:The research of production scheduling has developed rapidly in the past few decades, and people have done a lot of research on the models and methods of scheduling problems, because many practical scheduling problems belong to NP-complete problems. Classical scheduling theory and methods are still faced with various problems in solving practical scheduling problems. Intelligent optimal scheduling method is a simple and effective method to solve scheduling problems which has emerged in recent years. This kind of method is one of the most effective ways to solve the problem of practical scheduling, because it can obtain a more satisfactory scheduling scheme without the need of complicated mathematical models. In this paper, the equivalent parallel machine scheduling problem is studied. Firstly, the local search strategy of variable neighborhood descent (VND) is incorporated into the discrete differential evolutionary algorithm (DDEA) for the parallel machine scheduling model with the manufacturing period as the target. DDE_VND algorithm is proposed. Because this algorithm combines the advantages of DDE and VND, it improves the search performance and efficiency of DDE algorithm. Through the test of DDE_VND algorithm and DDE algorithm, the effectiveness of VND is proved. Under the same running conditions, the DDE VND algorithm is compared with the DDE algorithm and the genetic algorithm. The experimental results show that the DDE_VND algorithm is more effective. In addition, for the same parallel machine scheduling problem with total tardiness, the DDE_VND algorithm is further improved, and an improved due date rule is added to the DDE_VND algorithm for the initialization phase of the population. The improved MDDE_VND algorithm is obtained, and the validity of the rule is verified and compared by several examples. A standard example is used in the simulation experiment. The MDDE_VND algorithm is compared with DDE and Clone selective Particle Swarm Optimization (CSP) algorithm under the same running conditions. The excellent rate and the evolutionary convergence curve reflect the obvious advantages of the MDDE_VND algorithm. The parameter setting of the algorithm is discussed by using the ANOVA method of statistics, and a good set of parameter values are selected for the simulation experiment.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186

【参考文献】