Abstract
It is well known that job-shop scheduling problems with two jobs can be formulated as shortest path problems with obstacles in the plane. A reduction of this problem to an unrestricted shortest path problem in a special networkN is constructed inO (n logn) steps wheren is the number of obstacles. The shortest path inN can be found in timeO (n).
Zusammenfassung
Es ist bekannt, daß sich Job-Shop-Scheduling-Probleme mit zwei Jobs als kürzeste Wege-Probleme mit Hindernissen darstellen lassen. Gezeigt wird, daß sich ein solches Problem mit einem Aufwand vonO (n logn) auf ein normales kürzestes Wege-ProblemP reduzieren läßt, wennn die Anzahl der Hindernisse ist.P läßt sich überdies mit einem Aufwand vonO (n) lösen.
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
Akers, S. B.: A graphical approach to production scheduling problems. Operations Research4, 244–245 (1956).
Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms. Reading, Mass.: Addison-Wesley 1974.
Carlier, J., Pinson, E.: A branch and bound method for the job-shop problem. Technical Report, Institut de Mathématique Appliquées, Université de Angers, 1987.
Hardgrave, W. H., Nemhauser, G. L.: A geometric model and a graphical algorithm for a sequencing problem. Operations Research11, 889–900 (1963).
Hefetz, N., Adiri, I.: An efficient optimal algorithm for the two-machines, unit-time, jobshop, schedule-length problem. Mathematics of Operations Research7, 354–360 (1982).
Jackson, J. R.: An extension of Johnson's results on job lot scheduling. Naval Research Logistic Quarterly3, 201–203 (1956).
Muth, J. F., Thompson, G. L.: Industrial Scheduling. Englewood Cliffs, N. J.: Prentice-Hall 1963.
Szwarc, W.: Solution of the Akers-Friedman scheduling problem. Opertions Research8, 782–788 (1960).
Author information
Authors and Affiliations
Additional information
This work was partially supported by the Deutsche Forschungsgemeinschaft, Projekt CODIS.
Rights and permissions
About this article
Cite this article
Brucker, P. An efficient algorithm for the job-shop problem with two jobs. Computing 40, 353–359 (1988). https://doi.org/10.1007/BF02276919
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02276919