Abstract
In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.
Zusammenfassung
Mit dem Ziel der Minimierung der Gesamtbearbeitungszeit werden konstruktive Heuristiken für das open shop Problem betrachtet. Durch strukturelle Untersuchungen einer zulässigen Lösung werden zwei Arten von Heuristiken entwickelt: Konstruktion eines rangminimalen Bearbeitungsplanes durch sukzessives Lösen von gewichteten Matchingproblemen mit maximaler Kardinalität und Konstruktion einer Näherungslösung durch Anwendung von Einfügungstechniken kombiniert mit beam search. Die Verfahren werden an den aus der Literatur bekannten Benchmark Beispielen getestet. Die Resultate unserer Testrechnungen demonstrieren eindrucksvoll die Qualität unseres Einfügungsalgorithmus, insbesondere für wachsende Auftrags- und Maschinenzahl. Für 29 der 30 Benchmark Beispiele mit mindestens 10 Aufträgen und 10 Maschinen wird die mit Tabusuche ermittelte Näherungslösung verbessert.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bräsel, H.: Lateinische Rechtecke und Maschinenbelegung; Dissertation B, TU Magdeburg (1990).
Bräsel, H., Kleinau, M.: On the number of feasible schedules of the open-shop problem—an applicaton of special Latin rectangles. Optimization23, 251–260 (1992).
Bräsel, H., Tautenhahn, T.: Zur näherungsweisen Lösung eines open-shop Problems; Wiss. Z. TU Magdeburg33, 41–44 (1989).
Chen, B., Strusevitch, V.: Worst-case analysis of dense schedules for the three machine open shop scheduling. Preprint, Rotterdam (1991).
Glover, F.: Tabu Search—Part 1. ORSA J. Comput.1, 190–206 (1989).
Gonzales, T., Sahni, S.: Open-shop scheduling to minimize finish time. J. Assoc. Comput. Mach.23, 665–680 (1976).
Kleinau, U.: On some new methods for solving machine scheduling problems. Preprint, 16/91, TU Magdeburg (1991).
Lageweg, B. J., Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G.: Computer aided complexity classification of deterministic scheduling problems. Department of Operations Research, Statistics and System Theory, Report BW 138/81 (1981).
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., Shmoys, D. B.: Sequencing and scheduling: algorithms and complexity. Department of Operations Research, Statistics and System theory, Report BS-R8909 (1989).
Taillard, E.: Benchmarks for basic scheduling problems. ORWP89/21 (1989).
Taneav, V. S., Sotskov, Y. N., Strusewitch, V. A.: Theory of scheduling—multistage systems. Nauka, Moskau 1989) (in Russian).
Werner, F., Winkler, A.: Insertion techniques for the Heuristic solution of the job shop problem. to appear in Discrete Appl. Math.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bräsel, H., Tautenhahn, T. & Werner, F. Constructive heuristic algorithms for the open shop problem. Computing 51, 95–110 (1993). https://doi.org/10.1007/BF02243845
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02243845