A Giffler-Thompson genetic algorithm for the static job-shop scheduling problem

Abstract

As the job shop scheduling problem is a di±cult problem in combinatorial optimisation, a lot of research has been devoted to obtaining lower bounds for its objective function, in constructing branch-and-bound algorithms and in developing e±cient heuristics and meta-heuristics. Several genetic algorithms have been developed for the job-shop scheduling problem. The design of the genetic algorithms for the problem under study varies in the way of encoding a solution and in the use of its various operators. In this design of the genetic algorithm a crossover operator is developed based on principles set by Gi²er and Thompson to generate active schedules. Two alternative designs are tested on a number of benchmark problems. While performing well in general, the genetic algorithm performs rather poor on benchmark problems, which are known in the literature as extremely hard to solve. The genetic algorithm, as presented here, makes use of a parameter, which is believed to have an important influence on performance of the algorithm and of which an intelligent setting of its value might lead to promising results for the most di±cult job-shop scheduling problems.