Skip to main content
Springer Nature Link
Log in

Job-Shop Scheduling Problem

  • Reference work entry
Encyclopedia of Optimization

  • 238 Accesses

The job-shop problem may be formulated as follows. Given are n jobs j = 1,..., n and m machines M 1,..., M m . Job j consists of a sequence

of n j operations which must be processed in the given order, i.e. O i + 1, j cannot start before O ij is completed for i = 1,..., n j −1. Associated with each operation O ij there is a processing time p ij and a machine μ ij ∈{M 1,..., M m }. O ij must be processed for p ij time units on machine μ ij . Each job can be processed by at most one machine at a time and each machine can process only one operation at a time. If not stated differently preemptions of operations are not allowed. One has to find a feasible schedule which minimizes the makespan.

It is assumed that all processing times are nonnegative integers and that all jobs and machines are available at starting time zero. Furthermore, if not stated differently, machine repetition is allowed, i.e. μi + 1, j = μ ij is possible.

For a precise formulation of the job-shop problem, let be the...

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Reference

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

    MathSciNet  MATH  Google Scholar 

  2. Akers, S. B., and Friedman, J.: ‘A non-numerical approach to production scheduling problems’, Oper. Res.3 (1955), 429–442.

    Google Scholar 

  3. Applegate, D., and Cook, W.: ‘A computational study of the job-shop scheduling problem’, ORSA J. Comput.3 (1991), 149–156.

    MATH  Google Scholar 

  4. Balas, E., Lenstra, J. K., and Vazacopoulos, A.: ‘One machine scheduling with delayed precedence constraints’, Managem. Sci.41 (1995), 94–1096.

    MATH  Google Scholar 

  5. Blackstone, J. H., Phillips, D. T., and Hogg, G. L.: ‘A state of art survey of dispatching rules for manufacturing’, Internat. J. Production Res.20 (1982), 27–45.

    Google Scholar 

  6. Brinkkötter, W., and Brucker, P.: ’Solving open benchmark instances for the jobshop problem by parallel head-tail adjustments’, J. Scheduling (2000), to appear.

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  8. Brucker, P.: ‘A polynomial algorithm for the two machine job-shop scheduling problem with fixed number of jobs’, Oper. Res. Spektrum16 (1994), 5–7.

    Article  MathSciNet  MATH  Google Scholar 

  9. Brucker, P.: Scheduling algorithms, second ed., Springer 1998.

    Google Scholar 

  10. Brucker, P., and Jurisch, B.: ‘A new lower bound for the job-shop scheduling problem’, Europ. J. Oper. Res.64 (1993), 156–167.

    Article  MATH  Google Scholar 

  11. Brucker, P., Jurisch, B., and Sievers, B.: ‘A branch and bound algorithm for the job-shop problem’, Discrete Appl. Math.49 (1994), 107–127.

    Article  MathSciNet  MATH  Google Scholar 

  12. Brucker, P., Kravchenko, S. A., and Sotskov, Y. N.: ‘Preemptive job-shop scheduling problems with a fixed number of jobs’, Math. Meth. Oper. Res.49 (1999), 41–76.

    MathSciNet  MATH  Google Scholar 

  13. Carlier, J., and Pinson, E.: ‘An algorithm for solving the job-shop problem’, Managem. Sci.35 (1989), 164–176.

    MathSciNet  MATH  Google Scholar 

  14. Haupt, R.: ‘A survey of priority-rule based scheduling’, OR Spektrum11 (1989), 3–16.

    Article  MathSciNet  MATH  Google Scholar 

  15. Hefetz, N., and Adiri, I.: ‘An efficient algorithm for the two-machine unit-time jobshop schedule-length problem’, Math. Oper. Res.7 (1982), 354–360.

    MATH  Google Scholar 

  16. Jackson, J.R.: ‘An extension of Johnson’s results on job lot scheduling’, Naval Res. Logist. Quart.3 (1956), 201–203.

    Google Scholar 

  17. Kubiak, W., Sethi, S., and Sriskandarajah, C.: ‘An efficient algorithm for a job shop problem’, Ann. Oper. Res.57 (1995), 203–216.

    Article  MathSciNet  MATH  Google Scholar 

  18. Lenstra, J. K., and Rinnooy Kan, A. H. G.: ‘Computational complexity of discrete optimization problems’, Ann. Discrete Math.4 (1979), 121–140.

    Article  MathSciNet  MATH  Google Scholar 

  19. Lenstra, J. K., Rinnooy Kan, A. H. G., and Brucker, P.: ‘Complexity of machine scheduling problems’, Ann. Discrete Math.1 (1977), 343–362.

    Google Scholar 

  20. Martin, P. D., and Shmoys, D. B.: ‘A new approach to computing optimal schedules for the job shop scheduling problem’, Proc. 5th Internat. IPCO Conf. (1996).

    Google Scholar 

  21. Muth, J. F., and Thompson, G.L.: Industrial scheduling, Prentice-Hall 1963.

    Google Scholar 

  22. Nowicki, E., and Smutnicki, C.: ‘A fast tabu search algorithm for the job shop problem’, Managem. Sci.42 (1996), 797–813.

    MATH  Google Scholar 

  23. Panwalker, S.S., and Iskander, W.: ‘A survey of scheduling rules’, Oper. Res.25 (1977), 45–61.

    Article  Google Scholar 

  24. Sotskov, Y.N.: ‘On the complexity of shop scheduling problems with two or three jobs’, Europ. J. Oper. Res.53 (1991), 323–336.

    Article  Google Scholar 

  25. Sotskov, Y.N., and Shakhlevich, N.V.: ‘NP-hardness of shop-scheduling problems with three jobs’, Discrete Appl. Math.59 (1995), 237–266.

    Article  MathSciNet  MATH  Google Scholar 

  26. Timkovsky, V.G.: ‘On the complexity of scheduling an arbitrary system’, Soviet J. Comput. Syst. Sci.5 (1985).

    Google Scholar 

  27. Vaessens, R.J.M., Aarts, E.H.L., and Lenstra, J.K.: ‘Job shop scheduling by local search’, INFORMS J. Comput.8 (1996). Kluwer Academic Publishers Dordrecht

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachber. Math./Informatik Univ. Osnabrück, 49069, Osnabrück, Germany

    Peter Brucker

Authors
  1. Peter Brucker
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. Chemical Engin., Princeton Univ., Princeton, NJ, 08544-5263, USA

    Christodoulos A. Floudas

  2. Center for Applied Optim. Dept. Industrial and Systems Engin., Univ. Florida, Gainesville, FL, 32611, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Kluwer Academic Publishers

About this entry

Cite this entry

Brucker, P. (2001). Job-Shop Scheduling Problem . In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/0-306-48332-7_239

Download citation

  • DOI: https://doi.org/10.1007/0-306-48332-7_239

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-0-7923-6932-5

  • Online ISBN: 978-0-306-48332-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics