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...
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Reference
Adams, J., Balas, E., and Zawack, D.: ‘The shifting bottleneck procedure for job shop scheduling’, Managem. Sci.34 (1988), 391–401.
Akers, S. B., and Friedman, J.: ‘A non-numerical approach to production scheduling problems’, Oper. Res.3 (1955), 429–442.
Applegate, D., and Cook, W.: ‘A computational study of the job-shop scheduling problem’, ORSA J. Comput.3 (1991), 149–156.
Balas, E., Lenstra, J. K., and Vazacopoulos, A.: ‘One machine scheduling with delayed precedence constraints’, Managem. Sci.41 (1995), 94–1096.
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.
Brinkkötter, W., and Brucker, P.: ’Solving open benchmark instances for the jobshop problem by parallel head-tail adjustments’, J. Scheduling (2000), to appear.
Brucker, P.: ‘An efficient algorithm for the job-shop problem with two jobs’, Computing40 (1988), 353–359.
Brucker, P.: ‘A polynomial algorithm for the two machine job-shop scheduling problem with fixed number of jobs’, Oper. Res. Spektrum16 (1994), 5–7.
Brucker, P.: Scheduling algorithms, second ed., Springer 1998.
Brucker, P., and Jurisch, B.: ‘A new lower bound for the job-shop scheduling problem’, Europ. J. Oper. Res.64 (1993), 156–167.
Brucker, P., Jurisch, B., and Sievers, B.: ‘A branch and bound algorithm for the job-shop problem’, Discrete Appl. Math.49 (1994), 107–127.
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.
Carlier, J., and Pinson, E.: ‘An algorithm for solving the job-shop problem’, Managem. Sci.35 (1989), 164–176.
Haupt, R.: ‘A survey of priority-rule based scheduling’, OR Spektrum11 (1989), 3–16.
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.
Jackson, J.R.: ‘An extension of Johnson’s results on job lot scheduling’, Naval Res. Logist. Quart.3 (1956), 201–203.
Kubiak, W., Sethi, S., and Sriskandarajah, C.: ‘An efficient algorithm for a job shop problem’, Ann. Oper. Res.57 (1995), 203–216.
Lenstra, J. K., and Rinnooy Kan, A. H. G.: ‘Computational complexity of discrete optimization problems’, Ann. Discrete Math.4 (1979), 121–140.
Lenstra, J. K., Rinnooy Kan, A. H. G., and Brucker, P.: ‘Complexity of machine scheduling problems’, Ann. Discrete Math.1 (1977), 343–362.
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).
Muth, J. F., and Thompson, G.L.: Industrial scheduling, Prentice-Hall 1963.
Nowicki, E., and Smutnicki, C.: ‘A fast tabu search algorithm for the job shop problem’, Managem. Sci.42 (1996), 797–813.
Panwalker, S.S., and Iskander, W.: ‘A survey of scheduling rules’, Oper. Res.25 (1977), 45–61.
Sotskov, Y.N.: ‘On the complexity of shop scheduling problems with two or three jobs’, Europ. J. Oper. Res.53 (1991), 323–336.
Sotskov, Y.N., and Shakhlevich, N.V.: ‘NP-hardness of shop-scheduling problems with three jobs’, Discrete Appl. Math.59 (1995), 237–266.
Timkovsky, V.G.: ‘On the complexity of scheduling an arbitrary system’, Soviet J. Comput. Syst. Sci.5 (1985).
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
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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