zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A branch and bound method for the job-shop problem with sequence-dependent setup times. (English) Zbl 1152.90424
Summary: This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.

MSC:
90B35Scheduling theory, deterministic
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C39Dynamic programming
Software:
TSPTW
WorldCat.org
Full Text: DOI
References:
[1] Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job-shop scheduling. Management Science, 34, 391--401. · Zbl 0637.90051 · doi:10.1287/mnsc.34.3.391
[2] Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27, 219--239. · doi:10.1016/S0305-0483(98)00042-5
[3] Artigues, C., Belmokhtar, S., & Feillet, D. (2004). A new exact solution algorithm for the job shop problem with sequence-dependent setup times. In J. C. Régin & M. Rueher (Eds.), 1st international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems : Vol. 3011. Lecture notes in computer science (pp. 37--49). Berlin: Springer. · Zbl 1094.90553
[4] Artigues, C., Buscaylet, F., & Feillet, D. (2005a). Lower and upper bound for the job shop scheduling problem with sequence-dependent setup times. In Proceedings of the second multidisciplinary international conference on scheduling: theory and applications (MISTA’2005). New York.
[5] Artigues, C., Lopez, P., & Ayache, P. D. (2005b). Schedule generation schemes and priority rules for the job-shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operations Research, 138(1), 21--52. · Zbl 1091.90014 · doi:10.1007/s10479-005-2443-4
[6] Balas, E. (1996). New classes of efficiently solvable generalized traveling salesman problems (Technical Report #MSRR-615). Graduate School of Industrial Administration, Carnegie Mellon University.
[7] Balas, E., & Simonetti, N. (2001). Linear time dynamic programming algorithms for new classes of restricted TSPs. INFORMS, Journal on Computing, 13, 56--75. · Zbl 1238.90126 · doi:10.1287/ijoc.13.1.56.9748
[8] Balas, E., Simonetti, N., & Vazacopoulos, A. (2005). Job shop scheduling with setup-times, deadlines and precedence constraints. In Proceedings of the second multidisciplinary international conference on scheduling: theory and applications (MISTA’2005). New York. · Zbl 1168.90419
[9] Baptiste, P., Le Pape, C., & Nuijten, W. (2001). In Constraint-based scheduling : Vol. 39. International series in operations research & management science. Berlin: Springer.
[10] Blazewicz, J., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93(1), 1--33. · Zbl 0980.90024 · doi:10.1016/0377-2217(95)00362-2
[11] Brucker, P., & Thiele, O. (1996). A branch and bound method for the general-shop problem with sequence-dependent setup times. Operations Research Spektrum, 18, 145--161. · Zbl 0852.90087 · doi:10.1007/BF01539706
[12] Brucker, P., Jurisch, P., & Krämer, A. (1994a). The job-shop problem and immediate selection. Annals of Operations Research, 50, 73--114. · Zbl 0826.90062 · doi:10.1007/BF02085636
[13] Brucker, P., Jurisch, P., & Sievers, B. (1994b). A fast branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49, 107--127. · Zbl 0802.90057 · doi:10.1016/0166-218X(94)90204-6
[14] Buscaylet, F., & Artigues, C. (2003). A fast tabu search method for the job-shop problem with sequence-dependent setup times. In Metaheuristic international conference MIC’2003.
[15] Candido, M. A. B., Khator, S. K., & Barcias, R. M. (1998). A genetic algorithm based procedure for more realistic job shop scheduling problems. International Journal of Production Research, 36(12), 3437--3457. · Zbl 0946.90527 · doi:10.1080/002075498192148
[16] Carlier, J. (1982). The one machine sequencing problem. European Journal of Operational Research, 11, 42--47. · Zbl 0482.90045 · doi:10.1016/S0377-2217(82)80007-6
[17] Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35, 164--176. · Zbl 0677.90036 · doi:10.1287/mnsc.35.2.164
[18] Choi, I.-C., & Korkmaz, O. (1997). Job shop scheduling with separable sequence-dependent setups. Annals of Operations Research, 70, 155--170. · Zbl 0890.90094 · doi:10.1023/A:1018918003761
[19] Choi, I.-N., & Choi, D.-S. (2002). A local search algorithm for job-shop scheduling problems with alternative operations and sequence-dependent setups. Computers and Industrial Engineering, 42, 43--58. · doi:10.1016/S0360-8352(02)00002-5
[20] Conway, R. W., Maxwell, W. L., & Miller, L. W. (1967). Theory of scheduling. Reading: Addison--Wesley. · Zbl 1058.90500
[21] Demassey, S., Artigues, C., & Michelon, P. (2005). Constraint propagation-based cutting planes: an application to the resource-constrained project scheduling problem. INFORMS Journal on Computing, 17(1), 52--65. · Zbl 1239.90062 · doi:10.1287/ijoc.1030.0043
[22] Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3), 216--229. · Zbl 1056.90014 · doi:10.1002/net.20033
[23] Focacci, F., Laborie, P., & Nuijten, W. (2000). Solving scheduling problems with setup times and alternative resources. In Fifth international conference on artificial intelligence planning and scheduling (pp. 92--101).
[24] Focacci, F., Lodi, A., & Milano, M. (2002). A hybrid exact algorithm for the tsptw. INFORMS, Journal on Computing, 14, 403--417. · Zbl 1238.90054 · doi:10.1287/ijoc.14.4.403.2827
[25] Jain, A. S., & Meeran, S. (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2), 390--434. · Zbl 0938.90028 · doi:10.1016/S0377-2217(98)00113-1
[26] Kim, S. C., & Bobrowski, P. M. (1994). Impact of sequence-dependent setup time on job shop scheduling performance. International Journal of Production Research, 32(7), 1503--1520. · Zbl 0901.90130 · doi:10.1080/00207549408957019
[27] Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research, 90, 320--333. · Zbl 0916.90151 · doi:10.1016/0377-2217(95)00357-6
[28] Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement) (Technical report). Graduate School of Industrial Administration, Carnegie Mellon University.
[29] Martin, P., & Shmoys, D. B. (1996). A new approach to computing optimal schedules for the job-shop scheduling problem. In W. H. Cunningham, S. T. McCormick & M. Queyranne (Eds.), Proceedings of the 5th international conference on integer programming and combinatorial optimization IPCO’96 (pp. 389--403). Vancouver, British Columbia, Canada.
[30] Mason, S. J., Fowler, J. W., & Matthew Carlyle, W. (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 5(3), 247--262. · Zbl 1009.90045 · doi:10.1002/jos.102
[31] Noivo, J. A., & Ramalhinho-Lourenço, H. (1998). Solving two production scheduling problems with sequence-dependent set-up times (Technical Report No. 138). Department of Economics and Business, Universitat Pompeu Fabra, Barcelona.
[32] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42, 797--813. · Zbl 0880.90079 · doi:10.1287/mnsc.42.6.797
[33] Nuijten, W. P. M. (1994). Time and resource constrained scheduling: a constraint satisfaction approach. Eindhoven University of Technology: Ph.D. thesis. · Zbl 0837.90068
[34] Ovacik, I. M., & Uzsoy, R. (1992). A shifting bottleneck algorithm for scheduling semiconductor testing operations. Journal of Electronics Manufacturing, 2, 119--134. · doi:10.1142/S0960313192000157
[35] Ovacik, I. M., & Uzsoy, R. (1994a). Exploiting shop floor status information to schedule complex job shop. Journal of manufacturing systems, 13, 73--84. · doi:10.1016/0278-6125(94)90023-X
[36] Ovacik, I. M., & Uzsoy, R. (1994b). Rolling horizon algorithms for a single machine dynamic scheduling problem with sequence-dependent setup times. International Journal of Production Research, 32(6), 1243--1263. · Zbl 0901.90132 · doi:10.1080/00207549408956998
[37] Peridy, L. (1996). Le problème de job-shop: arbitrages et adjustments. Université de Technologie de Compiègne: Ph.D. thesis.
[38] Roy, B., & Sussman, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives (Technical Report Note DS No. 9bis). SEMA, Paris.
[39] Savelsberg, M. W. P. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4, 285--305. · doi:10.1007/BF02022044
[40] Schutten, J. M. J. (1995). Practical job shop scheduling (Technical Report LPOM-95-12). Laboratory of Production and Operations Management, Department of Mechanical Engineering, University of Twente, The Netherlands. · Zbl 0911.90221
[41] Sun, X., & Noble, J. S. (1999). A modified shifting bottleneck approach to job shop scheduling with sequence dependent setups. Journal of Manufacturing Systems, 18(6), 416--430. · doi:10.1016/S0278-6125(00)87643-8
[42] Torres, P., & Lopez, P. (2000). Overview and possible extensions of shaving techniques for job-shop problems. In Proceedings of the workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems, CPAIOR’00 (pp. 181--186). Paderborn, Germany.
[43] Vaessens, R. J. M., Aarts, E. H. L., & Lenstra, J. K. (1996). Job shop scheduling by local search. INFORMS Journal on Computing, 8, 302--317. · Zbl 0863.90094 · doi:10.1287/ijoc.8.3.302
[44] Vilím, P., & Barták, R. (2002). Filtering algorithms for batch processing with sequence dependent setup times. In M. Ghallab, J. Hertzberg & P. Traverso (Eds.), Proceedings of the sixth international conference on artificial intelligence planning and scheduling (AIPS 2002) (pp. 312--320). Menlo Park: AAAI Press.
[45] Wilbrecht, J. K., & Prescott, W. B. (1969). The influence of setup time on job shop performance. Management Science, 16(4), B274--B280. · doi:10.1287/mnsc.16.4.B274
[46] Zhou, C., & Egbelu, P. G. (1989). Scheduling in manufacturing shop with sequence-dependent setups. Robotics and Computer Integrated Manufacturing, 5, 73--81. · doi:10.1016/0736-5845(89)90031-8