EVOLUTION BASED LEARNING IN A JOB-SHOP SCHEDULING ENVIRONMENT

A class of approximation algorithms is described for solving the minim um makespan problem of job shop scheduling. A common basis of these al gorithms is the underlying genetic algorithm that serves as a meta-str ategy to guide an optimal design of local decision rule sequences. We consider sequences of dispatching rules for job assignment as well as sequences of one machine solutions in the sense of the shifting bottle neck procedure of Adams et al. Computational experiments show that our algorithm can find shorter makespans than the shifting bottleneck heu ristic or a simulated annealing approach with the same running time.