Zurück zu den Preprints des Jahres 2005


2005-30

Heuristic Algorithms for Open Shop Scheduling to Minimize Mean Flow Time, Part I: Constructive Algorithms

by Bräsel, H., Herms, A., Mörig, M., Tautenhahn, T., Tusch, J., Werner, F..


Series: 2005-30, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive 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. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m. In part II of this paper, several iterative algorithms are discussed and compared.

Keywords:
Open shop scheduling, Mean flow time, Constructive heuristics

This paper was published in:
European Journal of Operations Research, Vol. 189, 2008, 856 - 870 (under the title: Heuristic Constructive Algorithms for Open Shop Scheduling to Minimize Mean Flow Time).