进化规划方法在最小化拖期任务数并行机调度问题中的应用

Application of Evolutionary Programming Method in Parallel\=Machine Scheduling Problem of Minimizing the Number of Tardy Jobs

随着ＣＩＭＳ技术的发展，生产线调度问题的研究显得日益重要．最小化拖期任务数并行机调度问题是一类重要的生产线调度问题，但迄今为止，在解决工件和机器数较多的大规模并行机调度问题还存在着许多困难．进化规划方法与遗传算法一样是一种重要的进化计算方法，它具有描述简单、使用灵活、运行效率高、鲁棒性强、较少受初始条件限制等优点，这使得它有很高的实用价值，但与遗传算法相比，进化规划方法的应用还刚刚开始，特别是在生产调度领域的应用还很少见文献报导，进一步拓宽进化规划方法的应用领域很有意义．本文第一次将进化规划方法应用到最小化拖期任务数并行机调度问题中，并在问题的描述、可行解的表示、变异方法等方面作了研究．不同规模的计算实例表明了本文提出的进化规划算法是有效的，能用于解决较大规模并行机生产线调度问题，且解的质量优于启发式算法．

Studying job shop scheduling problem has become increasingly important with the development of CIMS.Identical parallel machine scheduling problem of minimizing the number of tardy jobs is a kind of important job 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,and its many advantages such as simple description,flexible usage,efficient running,good robustness,and less restriction from initial conditions,make it have great practical value.But compared with genetic algorithm,the application of evolutionary programming has just begun,and papers about the application of evolutionary programming in the field of production scheduling in particular are much fewer,so it is very worth while to develop further application fields of evolutionary programming method.In this paper,evolutionary programming method is applied to identical paallel machine scheduling problem of minimizing the number of tardy jobs for the first time.Researches are made in these aspects such as problem formulation,expression of feasible solution,mutation method of evolutionary programming and so on.Computational results of different scale problems justify the efficacy of the evolutionary programming algorithm,and that it is fit for solving larger scale identical parallel machine scheduling problem,and that the quality of its solution is superior to heuristic procedure.