×

Depth-first heuristic search for the job shop scheduling problem. (English) Zbl 1271.90035

Summary: We evaluate two variants of depth-first search algorithms and consider the classic job shop scheduling problem as a test bed. The first one is the well-known branch-and-bound algorithm proposed by P. Brucker et al. which uses a single chronological backtracking strategy. The second is a variant that uses partially informed depth-first search strategy instead. Both algorithms use the same heuristic estimation; in the first case, it is only used for pruning states that cannot improve the incumbent solution, whereas in the second it is also used to sort the successors of an expanded state. We also propose and analyze a new heuristic estimation which is more informed and more time consuming than that used by Brucker’s algorithm. We conducted an experimental study over well-known instances showing that the proposed partially informed depth-first search algorithm outperforms the original Brucker’s algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library; JOBSHOP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agnetis, A., Flamini, M., Nicosia, G., & Pacifici, A. (2011). A job-shop problem with one additional resource type. Journal of Scheduling, 14(3), 225–237. · Zbl 1222.90012 · doi:10.1007/s10951-010-0162-4
[2] Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3, 149–156. · Zbl 0755.90039 · doi:10.1287/ijoc.3.2.149
[3] Artigues, C., & Feillet, D. (2008). A branch and bound method for the job-shop problem with sequence-dependent setup times. Annals of Operations Research, 159(1), 135–159. · Zbl 1152.90424 · doi:10.1007/s10479-007-0283-0
[4] Balas, E., Simonetti, N., & Vazacopoulos, A. (2008). Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling, 11, 253–262. · Zbl 1168.90419 · doi:10.1007/s10951-008-0067-7
[5] Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling. Norwell: Kluwer Academic. · Zbl 1094.90002
[6] Beasley, J. E. (1990). Or-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069–1072. http://www.jstor.org/stable/2582903 .
[7] Beck, J. C. (2007). Solution-guided multi-point constructive search for job shop scheduling. The Journal of Artificial Intelligence Research, 29, 49–77. · Zbl 1182.68058
[8] Beck, J. C., & Fox, M. S. (2000). Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics. Artificial Intelligence, 117(1), 31–81. · Zbl 0939.68536 · doi:10.1016/S0004-3702(99)00099-5
[9] 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
[10] Blazewicz, J., Pesch, E., & Sterna, M. (2000). The disjunctive graph machine representation of the job shop scheduling problem. European Journal of Operational Research, 127(2), 317–331. · Zbl 0990.90035 · doi:10.1016/S0377-2217(99)00486-5
[11] Brinkkötter, W., &amp; Brucker, P. (2001). Solving open benchmark instances for the job-shop problem by parallel heads and tails adjustments. Journal of Scheduling, 4(1), 53–64. · Zbl 0979.90053 · doi:10.1002/1099-1425(200101/02)4:1<53::AID-JOS59>3.0.CO;2-Y
[12] Brucker, P. (2004). Scheduling algorithms (4th ed.). Berlin: Springer. · Zbl 1060.90034
[13] Brucker, P., &amp; Thiele, O. (1996). A branch and bound method for the general-job shop problem with sequence-dependent setup times. OR Spektrum, 18, 145–161. · Zbl 0852.90087 · doi:10.1007/BF01539706
[14] Brucker, P., Jurisch, B., &amp; Sievers, B. (1994a). A 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
[15] Brucker, P., Jurisch, B., &amp; Sievers, B. (1994b). Source code of a branch &amp; bound algorithm for the job shop scheduling problem. ftp://www.mathematik.uni-kl.de/pub/Math/ORSEP/BRUCKER2.ZIP . · Zbl 0802.90057
[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., &amp; Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2), 164–176. · Zbl 0677.90036 · doi:10.1287/mnsc.35.2.164
[18] Carlier, J., &amp; Pinson, E. (1990). A practical use of Jackson’s preemptive schedule for solving the job shop problem. Annals of Operations Research, 26, 269–287. · Zbl 0709.90061
[19] Dell’Amico, M., &amp; Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41, 231–252. · Zbl 0771.90056 · doi:10.1007/BF02023076
[20] Dorndorf, U., Pesch, E., &amp; Phan-Huy, T. (2000). Constraint propagation techniques for the disjunctive scheduling problem. Artificial Intelligence, 122, 189–240. · Zbl 0948.68010 · doi:10.1016/S0004-3702(00)00040-0
[21] Dorndorf, U., Pesch, E., &amp; Phan-Huy, T. (2002). Constraint propagation and problem decomposition: a preprocessing procedure for the job shop problem. Annals of Operations Research, 115, 125–145. · Zbl 1013.90057 · doi:10.1023/A:1021197120431
[22] Garcia, S., Fernández, A., Luengo, J., &amp; Herrera, F. (2010). Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power. Information Sciences, 180, 2044–2064. · Zbl 05758514 · doi:10.1016/j.ins.2009.12.010
[23] Garey, M., &amp; Johnson, D. (1979). Computers and intractability. New York: Freeman. · Zbl 0411.68039
[24] Gharbi, A., &amp; Labidi, M. (2010). Extending the single machine-based relaxation scheme for the job shop scheduling problem. Electronic Notes in Discrete Mathematics, 36, 1057–1064. · Zbl 1274.90145 · doi:10.1016/j.endm.2010.05.134
[25] Giffler, B., &amp; Thompson, G. L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8, 487–503. · Zbl 0248.90022 · doi:10.1287/opre.8.4.487
[26] González, M. A., Vela, C. R., González-Rodríguez, I., &amp; Varela, R. (2012). Lateness minimization with tabu search for job shop scheduling problem with sequence dependent setup times. Journal of Intelligent Manufacturing. doi: 10.1007/s10845-011-0622-5 . · Zbl 1184.90064
[27] González-Rodríguez, I., Puente, J., Vela, C. R., &amp; Varela, R. (2008). Semantics of schedules for the fuzzy job shop problem. IEEE Transactions on Systems, Man and Cybernetics. Part A. Systems and Humans, 38(3), 655–666. · doi:10.1109/TSMCA.2008.918603
[28] González-Rodríguez, I., Vela, C. R., Puente, J., &amp; Hernández-Arauzo, A. (2009). Improved local search for job shop scheduling with uncertain durations. In Proceedings of ICAPS 2009.
[29] Graham, R., Lawler, E., Lenstra, J., &amp; Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. · Zbl 0411.90044
[30] Guyon, O., Lemaire, P., Pinson, E., &amp; Rivreau, D. (2012). Solving an integrated job-shop problem with human resource constraints. Annals of Operations Research. doi: 10.1007/s10479-012-1132-3 . 1–25. · Zbl 1296.90046
[31] Hart, P., Nilsson, N., &amp; Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. · doi:10.1109/TSSC.1968.300136
[32] Harvey, W. D., &amp; Ginsberg, M. L. (1995). Limited discrepancy search. In Proceedings of IJCAI 1995 (Vol. 1, pp. 607–615).
[33] Korf, R. E. (1985). Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence, 27, 97–109. · Zbl 0573.68030 · doi:10.1016/0004-3702(85)90084-0
[34] Laborie, P. (2003). Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artificial Intelligence, 143(2), 151–188. · Zbl 1079.68622 · doi:10.1016/S0004-3702(02)00362-4
[35] Martin, P., &amp; Shmoys, D. B. (1996). A new approach to computing optimal schedules for the job-shop scheduling problem. In Proceedings of IPCO 1996 (pp. 389–403).
[36] Meeran, S., &amp; Morshed, M. S. (2011). A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study. Journal of Intelligent Manufacturing. doi: 10.1007/s10845-011-0520-x .
[37] Mencía, C., Sierra, M. R., &amp; Varela, R. (2010). Partially informed depth-first search for the job shop problem. In Proceedings of ICAPS 2010 (pp. 113–120).
[38] Mencía, R., Sierra, M. R., Mencía, C., &amp; Varela, R. (2011). Genetic algorithm for job-shop scheduling with operators. In LNCS: Vol. 6687. New challenges on bioinspired applications (pp. 305–314).
[39] Meseguer, P. (2012). Towards 40 years of constraint reasoning. Progress in Artificial Intelligence, 1(1), 25–43. doi: 10.1007/s13748-011-0006-2 . url: http://dx.doi.org/10.1007/s13748-011-0006-2 . · doi:10.1007/s13748-011-0006-2
[40] Nilsson, N. (1980). Principles of artificial intelligence. Palo Alto: Tioga. · Zbl 0422.68039
[41] Nowicki, E., &amp; Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145–159. · Zbl 1154.90479 · doi:10.1007/s10951-005-6364-5
[42] Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Reading: Addison-Wesley.
[43] Petrovic, S., Fayad, C., Petrovic, D., Burke, E., &amp; Kendall, G. (2008). Fuzzy job shop scheduling with lot-sizing. Annals of Operations Research, 159, 275–292. · Zbl 1152.90476 · doi:10.1007/s10479-007-0287-9
[44] Pinedo, M. (2008). Scheduling: theory, algorithms and systems (3rd ed.). Berlin: Springer. · Zbl 1155.90008
[45] Roy, B., &amp; Sussman, B. (1964). Les problemes d’ordonnancements avec contraintes disjonctives (Tech. Rep.). Notes DS No. 9 bis, SEMA, Paris.
[46] Sierra, M. R., Mencía, C., &amp; Varela, R. (2011). Optimally scheduling a job-shop with operators and total flow time minimization. In LNCS: Vol. 7023. Advances in artificial intelligence (pp. 193–202).
[47] Smith, S. F., &amp; Cheng, C. C. (1993). Slack-based heuristics for constraint satisfaction scheduling. In Proceedings of AAAI 1993 (pp. 139–144).
[48] Streeter, M. J., &amp; Smith, S. F. (2006). Exploiting the power of local search in a branch and bound algorithm for job shop scheduling. In Proceedings of ICAPS 2006 (pp. 324–333).
[49] Streeter, M. J., &amp; Smith, S. F. (2007). Using decision procedures efficiently for optimization. In Proceedings of ICAPS 2007 (pp. 312–319).
[50] Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285. · Zbl 0769.90052 · doi:10.1016/0377-2217(93)90182-M
[51] Van Laarhoven, P., Aarts, E., &amp; Lenstra, K. (1992). Job shop scheduling by simulated annealing. Operations Research, 40, 113–125. · Zbl 0751.90039 · doi:10.1287/opre.40.1.113
[52] Vela, C. R., Varela, R., &amp; González, M. A. (2010). Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times. Journal of Heuristics, 16(2), 139–165. · Zbl 1184.90064 · doi:10.1007/s10732-008-9094-y
[53] Watson, J. P., &amp; Beck, J. C. (2008). A hybrid constraint programming/local search approach to the job-shop scheduling problem. In Proceedings of CPAIOR 2008 (pp. 263–277). · Zbl 1142.68527
[54] Wu, T., Shi, L., &amp; Duffie, N. (2010). An HNP-MP approach for the capacitated multi-item lot sizing problem with setup times. IEEE Transactions on Automation Science and Engineering, 7(3), 500–511. doi: 10.1109/TASE.2009.2039134 . · doi:10.1109/TASE.2010.2042957
[55] Wu, T., Shi, L., Geunes, J., &amp; AkartunalI, K. (2011). An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging. European Journal of Operational Research, 214(2), 428–441. · Zbl 1218.90046 · doi:10.1016/j.ejor.2011.04.029
[56] Yau, H., &amp; Shi, L. (2009). Nested partitions for the large-scale extended job shop scheduling problem. Annals of Operations Research, 168(1), 23–39. · Zbl 1179.90168 · doi:10.1007/s10479-008-0370-x
[57] Zhang, C. Y., Li, P., Rao, Y., &amp; Guan, Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers &amp; Operations Research, 35, 282–294. · Zbl 1149.90345 · doi:10.1016/j.cor.2006.02.024
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.