Competitive genetic algorithms for the open-shop scheduling problem

For more than two machines, and when preemption is forbidden, the computati on of minimum makespan schedules for the open-shop problem is NP-hard. Comp ared to the flow-shop and the job-shop, the open-shop has free job routes w hich lead to a much larger solution space, to smaller gaps between the opti mal makespan and the lower bounds, and to disappointing results for the alg orithms based on the disjunctive graph model. For instance, the best existi ng branch and bound method cannot solve some 7 x 7 hard instances to optima lity, and all published metaheuristics (working by reversing some disjuncti ons already fixed) do not better than some greedy or steepest-descent heuri stics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for d etecting global optima disseminated among many quasi-optimal schedules. Thi s paper presents several GAs for the open-shop problem. It is shown that ev en simple and fast Versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each indi vidual has a distinct makespan, and a special procedure which reorders ever y new chromosome. Using problem-specific heuristics, it is possible to desi gn more powerful GAs which give excellent results, even on the hardest benc hmarks of the literature: for instance, all hard open instances from Tailla rd are broken, except one for which the best known solution is improved.