PARALLEL MACHINE SCHEDULING PROBLEMS USING MEMETIC ALGORITHMS

In this paper, we investigate how to apply the hybrid genetic algorith ms (the memetic algorithms) to solve the parallel machine scheduling p roblem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed m ethod is that (a) use the genetic algorithms to evolve the job partiti on and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computa tional experiments demonstrate that the hybrid genetic algorithm outpe rforms the genetic algorithms and the conventional heuristics. (C) 199 7 Elsevier Science Ltd.