zbMATH — the first resource for mathematics

A branch and bound algorithm for the job-shop scheduling problem. (English) Zbl 0802.90057
A fast branch-and-bound algorithm for the job-shop scheduling problem is described. Among other hard problems it solves to optimality the \(10\times 10\) benchmark problem which has been open for a long time. Implementation on a workstation and encouraging computational results are presented.

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job-shop scheduling, Management sci., 34, 391-401, (1988) · Zbl 0637.90051
[2] Applegate, D.; Cook, W., A computational study of job shop scheduling, CMU-CS-90-145, ORSA J. comput., 3, 149-156, (1991) · Zbl 0755.90039
[3] Bouma, R.W., Job-shop scheduling: A comparison of three enumeration schemes in a branch and bound approach, ()
[4] Brucker, P.; Jurisch, B., A new lower bound for the job-shop scheduling problem, European J. oper. res., 64, 156-167, (1993) · Zbl 0778.90022
[5] Brucker, P.; Jurisch, B.; Sievers, B., Job-shop (C-codes), European J. oper. res., 57, 132-133, (1992)
[6] Carlier, J., One machine problem, European J. oper. res., 11, 42-47, (1982) · Zbl 0482.90045
[7] Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management sci., 35, 164-176, (1989) · Zbl 0677.90036
[8] Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job shop problem, Ann. oper. res., 26, 269-287, (1990) · Zbl 0709.90061
[9] Grabowski, J.; Nowicki, E.; Smutnicki, C., Algorytm blokowy szeregowania operacji w systemie gniazdowyn, Przeglad statystyczny R. XXXXV, 1, 67-80, (1988), zeszyt
[10] Grabowski, J.; Nowicki, E.; Zdrzalka, S., A block approach for single machine scheduling with relase dates and due dates, European J. oper. res., 26, 278-285, (1986) · Zbl 0603.90073
[11] B. Jurisch and B. Sievers, Ein Branch and Bound Verfahren für des Job-Shop Scheduling Problem, Osnabrück. Schrift. Math. Reihe P, Heft 122. · Zbl 0802.90057
[12] van Laarhoven, P.J.M.; Aarts, E.H.L.; Lenstra, J.K., Job shop scheduling by simulated annealing, Oper. res., 40, 113-125, (1992) · Zbl 0751.90039
[13] Lenstra, J.K.; Rinnooy Kan, A.H.G.; Brucker, P., Complexity of machine scheduling problems, (), 343-362 · Zbl 0301.90025
[14] Muth, J.F.; Thompson, G.L., Industrial scheduling, (1963), Prentice-Hall Englewood Cliffs, NJ
[15] B. Roy and B. Sussmann, Les problèmes d’ordonnancement avec contraintes disjonctives, Note DS no. 9 bis, SEMA, Paris.
[16] M. Widmer, Job-shop scheduling with tooling constraints: a tabu search approach, OR working paper 89/22, Département of Mathématiques, Ecole Polytechnique Fédérale de Lausanne.
[17] McMahon, G.; Florian, M., On scheduling with ready times and due dates to minimize maximum lateness, Oper. res., 23, 475-482, (1975) · Zbl 0301.90024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.