Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Job-shop scheduling with multi-purpose machines

Scheduling-Probleme in Jop-Shops mit Mehrzweckmaschinen

  • Published:
Computing Aims and scope Submit manuscript

Abstract

Consider the following generalization of the classical job-shop scheduling problem in which a set of machines is associated with each operation of a job. The operation can be processed on any of the machines in this set. For each assignment μ of operations to machines letP(μ) be the corresponding job-shop problem andf(μ) be the minimum makespan ofP(μ). How to find an assignment which minimizesf(μ)? For problems with two jobs a polynomial algorithm is derived.

Zusammenfassung

Folgende Verallgemeinerung des klassischen Job-Shop Scheduling Problems wird untersucht. Jeder Operation eines Jobs sei eine Menge von Maschinen zugeordnet. Wählt man für jede Operation genau eine Maschine aus dieser Menge aus, so erhält man ein klassisches Job-Shop Problem, dessen minimale Gesamtbearbeitungszeitf(μ) von dieser Zuordnung μ abhängt. Gesucht ist eine Zuordnung μ, dief(μ) minimiert. Für zwei Jobs wird ein polynomialer Algorithmus entwickelt, der dieses Problem löst.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Akers, S. B., A graphical approach to production scheduling problems. Operations Research4, 244–245 (1956).

    Google Scholar 

  2. Brucker, P., An efficient algorithm for the job-shop problem with two jobs, Computing40, 353–359 (1988).

    Google Scholar 

  3. Hardgrave, W. H., Nemhauser, G. L., A geometric model and a graphical algorithm for a sequencing problem. Operations Research11, 889–900 (1963).

    Google Scholar 

  4. Sotskov, Y. N., The complexity of shop-scheduling problems with two or three jobs. European Journal of Operations Research (in press).

  5. Szwarc, W., Solution of the Akers-Friedman scheduling problem. Operations Research8, 782–788 (1960).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik/Informatik, Universität Osnabrück, Albrechtstrasse 28, D-4500, Osnabrück, Federal Republic of Germany

    P. Brucker & R. Schlie

Authors
  1. P. Brucker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Schlie
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brucker, P., Schlie, R. Job-shop scheduling with multi-purpose machines. Computing 45, 369–375 (1990). https://doi.org/10.1007/BF02238804

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02238804

AMS Subject Classification

Key words

Search

Navigation