A comparison of heuristics for mean flow time open shop scheduling
Information Control Problems in Manufacturing, Volume # 12 | Part# 1
Heidemarie Brasel; Andre Herms; Marc Morig; Thomas Tautenhahn; Jan Tusch; Frank Werner; Per Willenius
Digital Object Identifier (DOI)
In this paper, the problem of scheduling n jobs on m machines in an open shop environment is considered so that mean flow time becomes minimal. Since this problem is strongly NP-hard, different 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 flow time.
 Achugbue, J.O. and F.Y. Chin (1982). Scheduling the open shop to minimize mean flow time. SIAM J. on Computing 11, 709-720.  Alcaide, D., J. Sicilia and D. Vigo (1997). A tabu search algorithm for the open shop problem. Top 5, 283-286.  Blum, C. (2005). Beam-aco - hybridizing ant colony optimization with beam search: An application to open shop scheduling. Comput. Oper. Res. 32, 1595-1591.  Bräsel, H. and H. Hennes (2004). On the open-shop problem with preemption and minimizing the average completion time. European J. Oper. Res. 157, 607-619.  Bräsel, H., T. Tautenhahn and F. Werner (1993). Constructive heuristic algorithms for the open-shop problem. Computing 51, 95-110.  Brucker, P., J. Hurink, B. Jurisch and B. Wöstmann (1997). A branch-and-bound algorithm for the open-shop problem. Discrete Applied Mathematics 76, 43-59.  Dorndorf, U., E. Pesch and T. Phan-Huy (2001). Solving the open shop scheduling problem. Journal of Scheduling 4, 157-174.  Gonzalez, S. and T. Sahni (1976). Open shop scheduling to minimize finish time. J. Assoc. of Comput. Mach. 23, 665-679.  Gueret, C., N. Jussien and C. Prins (2000). Using intelligent backtracking to improve branch-and-bound methods: An application to open-shop problems. European J. Oper. Res. 127, 344-354.  Kubiak, W., C. Sriskandarajah and K. Zaras (1991). A note on the complexity of open shop scheduling problems. INFOR 29, 284-294.  Liaw, C.-F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European J. Oper. Res. 124, 28-42.  Liaw, C.-F., C.-Y. Cheng and M. Chen (2002). The total completion time open shop scheduling problem with a given sequence of jobs on one machine. Comput. Oper. Res. 29, 1251- 1266.  Liu, C.Y. and R.L. Bulfin (1987). Scheduling ordered open shops. Comput. Oper. Res. 14, 257-264.  Prins, C. (1994). An overview of scheduling problems arising in satellite communications. Journal Oper. Res. Soc. 40, 611-623.  Queyranne, M. and M. Sviridenko (2002). Approximation algorithms for shop scheduling problems with minsum objective. Journal of Scheduling 5, 287-305.  Werner, F. and A. Winkler (1995). Insertion techniques for the heuristic solution of the job shop problem. Discrete Appl. Math. 50, 191- 211.