The job-shop problem and immediate selection | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

The job-shop problem and immediate selection

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The job-shop problem is one of the most difficult NP-hard scheduling problems. A 10×10-problem published in 1963 has been solved only recently by Carlier and Pinson using a branch and bound method. Other branch and bound algorithms have been developed recently. The efficiency of all these branch and bound methods relies on the concept of immediate selection which allows to introduce order relations on the setI of all operations to be processed on the same machine before branching. We present new algorithms for immediate selection. Among them are

  1. •

    anO(max {n logn,f})-algorithm for fixing all disjunctions induced by cliques;

  2. •

    anO(n 2)-algorithm based on concepts which are different from those used by Carlier and Pinson.

Here,n is the number of operations inI andf is the number of induced order relations.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job-shop scheduling, Manag. Sci. 34(1988)391–401.

    Google Scholar 

  2. D. Applegate and W. Cook, A computational study of the job shop scheduling problem, ORSA J. Comp. 3(1991)149–156.

    Google Scholar 

  3. P. Brucker, B. Jurisch and B. Sievers, A branch and bound algorithm for the job-shop scheduling problem(1991), to appear in Discr. Appl. Math.

  4. J. Carlier, One machine sequencing problem, Eur. J. Oper. Res. 11(1982)42–47.

    Google Scholar 

  5. J. Carlier and E. Pinson, An algorithm for solving the job-shop problem, Manag. Sci. 35(1989)164–176.

    Google Scholar 

  6. J. Carlier and E. Pinson, A practical use of Jackson's preemptive schedule for solving the job shop problem, Ann. Oper. Res. 26(1990)269–287.

    Google Scholar 

  7. G. Deweß, An existence theorem for packing problems with implications for the computation of optimal machine schedules, Optimization 25(1992)261–269.

    Google Scholar 

  8. M.J. Fischer and A.R. Meyer, Boolean matrix multiplication and transitive closure,12th Annual Symp. on Switching and Automata Theory, East Lansing, MI (1971) pp. 129–137.

  9. J.F. Muth and G.L. Thompson,Industrial Scheduling (Prentice Hall, Englewood Cliffs, NJ, 1963).

    Google Scholar 

  10. B. Roy and B. Sussmann, Les Problèmes d'ordonnancement avec contraintes disjonctives, Note DS no. 9 bis, SEMA, Paris (1964).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik/Informatik, Universität Osnabrück, D-49069, Osnabrück, Germany

    Peter Brucker, Bernd Jurisch & Andreas Krämer

Authors
  1. Peter Brucker
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Bernd Jurisch
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Andreas Krämer
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

Supported by the Deutsche Forschungsgemeinschaft, Project JoPTAG.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brucker, P., Jurisch, B. & Krämer, A. The job-shop problem and immediate selection. Ann Oper Res 50, 73–114 (1994). https://doi.org/10.1007/BF02085636

Download citation

  • Issue Date:

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

Keywords