资源受限单机动态调度的并行GA算法研究

研究资源受限系统动态调度问题,针对时序约束问题提出一种并行遗传算法(PGA)。给出满足排序优先次序约束的一种基因编码方法;采用不破坏优先级可行性的交叉操作,并予以证明;建立一种并行处理机制,使搜索避免出现局优现象。在技术允许情况下,单机动态调度引入抢占式加工方式,会一定程度上提高系统的性能。通过仿真试验验证,并行GA算法可兼顾优化效果和计算效率,解决单机动态调度问题。

We consider the resource-constrained dynamic scheduling problem. Traditional genetic algorithms (GA) often meet the occurrence of slow convergence. We introduce the parallel search mechanism into genetic algorithms to avoid the shortage above-mentioned. Parallel genetic algorithm (PGA) is proposed for solving sequence-constrained problems. We adopt the permutation-based coding with satisfaction of priority requirements. An individual chromosome is given by an activity sequence. The crossover operator is customized by the research project. We also prove that the crossover operator results in a precedence feasible offspring genotype if applied to precedence feasible parent individuals. With the technological permission, single-machine preemptive scheduling will improve the performance of scheduling system. Simulation results show that our parallel genetic algorithm gains excellent effectiveness and efficiency for single-machine dynamic scheduling.

973计划课题(2002CB312200);;国家“十五”攻关重点专项基金资助项目(2001BA206A)