» Download Article

Authors
Heidemarie Brasel; Andre Herms; Marc Morig; Thomas Tautenhahn; Jan Tusch; Frank Werner; Per Willenius

Digital Object Identifier (DOI)
10.3182/20060517-3-FR-2903.00072

Page Numbers:
119-124

Index Terms
schedule algorithms,multimachine,optimization,implementation

Abstract
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.

References

[1] Achugbue, J.O. and F.Y. Chin (1982). Scheduling
    the open shop to minimize mean flow time.
    SIAM J. on Computing 11, 709-720.
[2] Alcaide, D., J. Sicilia and D. Vigo (1997). A tabu
    search algorithm for the open shop problem.
    Top 5, 283-286.
[3] Blum, C. (2005). Beam-aco - hybridizing ant
    colony optimization with beam search: An
    application to open shop scheduling. Comput.
    Oper. Res. 32, 1595-1591.
[4] 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.
[5] Bräsel, H., T. Tautenhahn and F. Werner (1993).
    Constructive heuristic algorithms for the
    open-shop problem. Computing 51, 95-110.
[6] 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.
[7] Dorndorf, U., E. Pesch and T. Phan-Huy (2001).
    Solving the open shop scheduling problem.
    Journal of Scheduling 4, 157-174.
[8] Gonzalez, S. and T. Sahni (1976). Open shop
    scheduling to minimize finish time. J. Assoc.
    of Comput. Mach. 23, 665-679.
[9] 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.
[10] Kubiak, W., C. Sriskandarajah and K. Zaras
     (1991). A note on the complexity of open shop
     scheduling problems. INFOR 29, 284-294.
[11] Liaw, C.-F. (2000). A hybrid genetic algorithm for
     the open shop scheduling problem. European
     J. Oper. Res. 124, 28-42.
[12] 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.
[13] Liu, C.Y. and R.L. Bulfin (1987). Scheduling
     ordered open shops. Comput. Oper. Res.
     14, 257-264.
[14] Prins, C. (1994). An overview of scheduling
     problems arising in satellite communications.
     Journal Oper. Res. Soc. 40, 611-623.
[15] Queyranne, M. and M. Sviridenko (2002). Approximation
      algorithms for shop scheduling
     problems with minsum objective. Journal of
     Scheduling 5, 287-305.
[16] Werner, F. and A. Winkler (1995). Insertion techniques
      for the heuristic solution of the job
     shop problem. Discrete Appl. Math. 50, 191-
     211.