Comparison of heuristics for mean flow time in open shop scheduling

Abstract: In this paper, the problem of scheduling n jobs on m machines in an open shop environment is considered so that mean ow time becomes minimal. Since this problem is strongly NP-hard, dierent constructive and iterative heuristic algorithms are developed and discussed. Computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is estimated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimation of mean ow time. Copyright c IFAC 200