×

zbMATH — the first resource for mathematics

Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis. (English) Zbl 1267.68217
A core constraint-based search procedure embedded within a larger iterative-sampling search framework is proposed for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max).
The core constraint-based search procedure generates a consistent ordering of activities that require the same resource by incrementally adding precedence constraints between activity pairs belonging to a temporally feasible solution. The search procedure is a conflict sampling method biased toward selection of the most critical conflicts coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. The iterative sampling procedure is not tailored to the job-shop problem in any way and it aims at broadening the search space coverage and promoting solution optimization.
The effectiveness of the overall heuristic algorithm is demonstrated by performing a set of experiments on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W20 Randomized algorithms
Software:
R; race
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job shop scheduling. Manage. Sci. 34(3), 391–401 (1988) · Zbl 0637.90051 · doi:10.1287/mnsc.34.3.391
[2] Allahverdi, A., Soroush, H.: The significance of reducing setup times/setup costs. Eur. J. Oper. Res. 187(3), 978–984 (2008) · Zbl 1137.90475 · doi:10.1016/j.ejor.2006.09.010
[3] Allahverdi, A., Ng, C., Cheng, T., Kovalyov, M.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985–1032 (2008) · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060
[4] Artigues, C., Feillet, D.: A branch and bound method for the job-shop problem with sequence-dependent setup times. Ann. Oper. Res. 159(1), 135–159 (2008) · Zbl 1152.90424 · doi:10.1007/s10479-007-0283-0
[5] Balas, E., Simonetti, N., Vazacopoulos, A.: Job shop scheduling with setup times, deadlines and precedence constraints. J. Sched. 11(4), 253–262 (2008) · Zbl 1168.90419 · doi:10.1007/s10951-008-0067-7
[6] Birattari, M.: Race: Racing methods for the selection of the best. http://CRAN.R-project.org/package=race , R package version 0.1.58 (2010)
[7] Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.,: A racing algorithm for configuring metaheuristics. In: GECCO, pp. 11–18 2002
[8] Brucker, P., Jurisch, B., Sievers, B.: A branch and bound algorithm for the job-shop scheduling problem. Discrete Appl. Math. 49(1–3), 107–127 (1994) · Zbl 0802.90057 · doi:10.1016/0166-218X(94)90204-6
[9] Brucker, P., Thiele, O.: A branch & bound method for the general-shop problem with sequence dependent setup-times. OR Spectrum 18(3), 145–161 (1996) · Zbl 0852.90087 · doi:10.1007/BF01539706
[10] Brucker, P., Lenstra, J., Kan, A.R.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362 (1977) · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X
[11] Cambazard, H., Hebrard, E., Barry, O., Papadopoulos, A.: Local search and constraint programming for the post-enrolment-based course timetabling problem. In: PATAT ’08–Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (2008) · Zbl 1251.90120
[12] Cesta, A., Oddi, A., Smith, S.F.: A constraint-based method for project scheduling with time windows. J. Heuristics 8(1), 109–136 (2002) · Zbl 1048.90103 · doi:10.1023/A:1013617802515
[13] Cheng, C., Smith, S.: Generating feasible schedules under complex metric constraints. In: Proceedings 12th National Conference on AI (AAAI-94) (1994)
[14] Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artif. Intell. 49, 61–95 (1991) · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6
[15] Demirkol, E., Mehta, S., Uzsoy, R.: Benchmarks for shop scheduling problems. Eur. J. Oper. Res. 109(1), 137–141 (1998) · Zbl 0951.90022 · doi:10.1016/S0377-2217(97)00019-2
[16] Focacci, F., Laborie, P., Nuijten, W.: Solving scheduling problems with setup times and alternative resources. In: AIPS, pp. 92–111 (2000)
[17] González, M.A., Vela, C.R., Varela, R.: A Tabu search algorithm to minimize lateness in scheduling problems with setup times. In: Proceedings of the CAEPIA-TTIA 2009 13th Conference of the Spanish Association on Artificial Intellegence (2009)
[18] Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95–132 (1974) · Zbl 0284.68074 · doi:10.1016/0020-0255(74)90008-5
[19] Nowicki, E., Smutnicki, C.: An advanced tabu search algorithm for the job shop problem. J. Sched. 8(2), 145–159 (2005) · Zbl 1154.90479 · doi:10.1007/s10951-005-6364-5
[20] Oddi, A., Smith, S.: Stochastic procedures for generating feasible schedules. In: Proceedings 14th National Conference on AI (AAAI-97), pp. 308–314 (1997)
[21] Ovacik, I., Uzsoy, R.: Exploiting shop floor status information to schedule complex job shops. J. Manuf. Syst. 13(2), 73–84 (1994) · doi:10.1016/0278-6125(94)90023-X
[22] Ovacik, I., Uzsoy, R.: Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic, Dordrecht (1997) · Zbl 0911.90217
[23] Policella, N., Cesta, A., Oddi, A., Smith, S.: From precedence constraint posting to partial order schedules. AI Commun. 20(3), 163–180 (2007) · Zbl 1146.90421
[24] R Development Core Team (2010) R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, http://www.R-project.org/ . ISBN 3-900051-07-0 (2010)
[25] Sotskov, Y.N., Shakhlevich, N.V.: Np-hardness of shop-scheduling problems with three jobs. Discrete Appl. Math. 59(3), 237–266 (1995). doi: 10.1016/0166-218X(93)E0169-Y · Zbl 0837.90072
[26] Vela, C.R., Varela, R., González, MA.: Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times. J. Heuristics 16(2):139–165 (2008). http://www.springerlink.com/index/10.1007/s10732-008-9094-y · Zbl 1184.90064 · doi:10.1007/s10732-008-9094-y
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.