Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482004 | European Journal of Operational Research | 2008 | 15 Pages |
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 evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Heidemarie Bräsel, André Herms, Marc Mörig, Thomas Tautenhahn, Jan Tusch, Frank Werner,