摘要
并行多机调度问题是一类重要的车间调度问题，但迄今为止，在解决工件和机器数较多的大规模并行多机调度问题还存在着许多困难。进化规划方法与遗传算法一样是一种重要的进化计算方法，但与遗传算法相比，进化规划算法的应用还刚刚开始，特别是在调度领域的应用还很少见文献报道，第一次将进化规划方法应用到并行多机调度问题中，并在问题的描述、可行解的表示、变异方法、提高进化规划方法的局部寻优能力等方面作了研究。不同规模的计算实例表明了本文提出的进化规划算法是有效的，能用于解决较大规模并行多机调度问题，且解的质量优于启发式算法和模拟退火算法。
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.
出处
《清华大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
1998年第8期100-103,共4页
Journal of Tsinghua University(Science and Technology)
基金
国家"八六三"高技术项目
关键词
并行多机
进化规划
组合优化
车间
调度问题
identical parallel machine
evolutionary programming
combinatorial optimization
scheduling problem
