进化规划方法在并行多机调度问题中的应用

并行多机调度问题是一类重要的车间调度问题，但迄今为止，在解决工件和机器数较多的大规模并行多机调度问题还存在着许多困难。进化规划方法与遗传算法一样是一种重要的进化计算方法，但与遗传算法相比，进化规划算法的应用还刚刚开始，特别是在调度领域的应用还很少见文献报道，第一次将进化规划方法应用到并行多机调度问题中，并在问题的描述、可行解的表示、变异方法、提高进化规划方法的局部寻优能力等方面作了研究。不同规模的计算实例表明了本文提出的进化规划算法是有效的，能用于解决较大规模并行多机调度问题，且解的质量优于启发式算法和模拟退火算法。

Application of evolutionary programming method in identical parallel machine scheduling problem

Studying shop scheduling problem has become increasingly important with the development of CIMS. Identical parallel machine scheduling problem is a kind of important shop scheduling problem, but there have been many difficulties in the course of solving large scale identical parallel machine scheduling problem with too many jobs and machines so far. Evolutionary Programming method is an important evolutionary computation method as genetic algorithm. But compared with genetic algorithm, the application of evolutionary programming has just begun, papers about the application of evolutionary programming in the field of scheduling are much fewer, in this paper, evolutionary programming method is applied to identical parallel machine scheduling problem for the first time. researches are made in these aspects such as problem formulation, expression of feasible solution, mutation method of evolutionary programming and improving the ability of local optimization of evolutionary programming. Computational results of different scale problems show that the evolutionary programming algorithm is efficient, and that it is fit for solving larger scale identical parallel machine scheduling problem, and that the quality of its solution has advantage over heuristic procedure and simulated annealing.