A knowledge-based evolutionary strategy for scheduling problems with bottlenecks

In this paper we confront a family of scheduling problems by means of genetic algorithms: the job shop scheduling problem with bottlenecks. Our main contribution is a strategy to introduce specific knowledge into the initial population. This strategy exploits a probabilistic-based heuristic method that was designed to guide a conventional backtracking search. We report experimental results on two benchmarks, the first one includes a set of small problems and is taken from the literature. The second includes medium and large size problems and is proposed by us. The experimental results show that the performance of the genetic algorithm clearly augments when the initial problem is seeded with heuristic chromosomes, the improvement being more and more appreciable as long as the size of the problem instance increases. Moreover premature convergence which sometimes appears when randomness is limited in any way in a genetic algorithm is not observed.