Abstract
We propose a novel, exact any-time search strategy that combines iterative deepening \(\text{ A}\)* (\(\text{ IDA}\)*) with depth-first search and we consider the job shop scheduling problem with makespan minimization as a test bed. The combination of these search strategies is done so that limited depth-first searches are issued from some of the states distributed along the frontier reached by \(\text{ IDA}\)* in each iteration. In this way, a proper equilibrium between intensification and diversification search effort is achieved while the algorithm keeps the capability of obtaining tight lower bounds. To evaluate the proposed strategy and to compare it with other methods, we have conducted an experimental study involving a number of conventional benchmarks with instances of various sizes. The results of these experiments show that the proposed algorithm takes less time than other methods in reaching optimal solutions for small and medium-size instances, and that it is quite competitive in reaching good solutions and good lower bounds for the instances that cannot be optimally solved.
Similar content being viewed by others
Notes
In the context of graph search the notion of transposition refers to the existence of many paths connecting the same pair of states.
We consider minimization problems w.l.o.g.
References
Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal of Computing, 3, 149–156.
Balas, E., & Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2), 262–275.
Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling. Norwell, MA: Kluwer.
Beasley, J. E. (1990). Or-library: Distributing test problems by electronic mail. The Journal of the Operational Research Society 41(11), 1069–1072. http://www.jstor.org/stable/2582903.
Beck, J. C. (2007). Solution-guided multi-point constructive search for job shop scheduling. Journal of Artificial Intelligence Research (JAIR), 29, 49–77.
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.
Brinkkötter, W., & 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.
Brucker, P., Jurisch, B., & Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49, 107–127.
Carlier, J., & Pinson, E. (1990). A practical use of Jackson’s preemptive schedule for solving the job shop problem. Annals of Operations Research, 26, 269–287.
Chakrabarti, P. P., Ghose, S., Acharya, A., & Sarkar, S. C. D. (1989). Heuristic search in restricted memory. Artificial Intellignce, 41(2), 197–221.
Coego, J., Mandow, L., & Pérez de la Cruz, J. (2009). A new approach to iterative deepening multiobjective A. In AI*IA, pp 264–273.
Coego, J., Mandow, L., & Pérez de la Cruz, J. (2012). A comparison of multiobjective depth-first algorithms. Journal of Intelligent Manufacturing, 1–9. doi:10.1007/s10845-012-0632-y.
Dell’ Amico, M., & Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41, 231–252.
Dorndorf, U., Pesch, E., & Phan-Huy, T. (2000). Constraint propagation techniques for the disjunctive scheduling problem. Artificial Intelligence, 122, 189–240.
García, S., Fernández, A., Luengo, J., & 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(10), 2044–2064.
Garey, M., & Johnson, D. (1979). Computers and intractability. San Francisco, CA: Freeman.
Gharbi, A., & Labidi, M. (2010). Extending the single machine-based relaxation scheme for the job shop scheduling problem. Electronic Notes in Discrete Mathematics, 36, 1057–1064.
Giffler, B., & Thompson, G. L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8, 487–503.
González, M. A., Vela, C. R., González-Rodríguez, I., & Varela, R. (2012). Lateness minimization with tabu search for job shop scheduling problem with sequence dependent setup times. Jornal of Intelligent Manufacturing. doi:10.1007/s10845-011-0622-5.
González Rodríguez, I., Vela, C. R., & Puente, J. (2010). A genetic solution based on lexicographical goal programming for a multiobjective job shop with uncertainty. Journal of Intelligent Manufacturing, 21, 65–73.
Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.
Harikumar, S., & Kumar, S. (1996). Iterative deepening multiobjective A. Information Processing Letters, 58(1), 11–15.
Harvey, W. D., & Ginsberg, M. L. (1995). Limited discrepancy search. In Proceedings of IJCAI 1995 (1), pp. 607–615.
Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27, 97–109.
Korf, R. E., Reid, M., & Edelkamp, S. (2001). Time complexity of iterative-deepening-\(\text{ A}^{*}\). Artificial Intelligence, 129(1–2), 199–218.
Laborie, P. (2003). Algorithms for propagating resource constraints in ai planning and scheduling: Existing approaches and new results. Artificial Intellignece, 143(2), 151–188.
Mattfeld, D. (1995). Evolutionary search and the job shop investigations on genetic algorithms for production scheduling. Berlin: Springer.
Meeran, S., & Morshed, M. (2011). A hybrid genetic tabu search algorithm for solving job shop scheduling problems: A case study. Journal of Intelligent Manufacturing, 23(4), 1063–1078.
Mencía, C., Sierra, M. R., & Varela, R. (2010). Partially informed depth-first search for the job shop problem. In Proceedings of ICAPS 2010, pp. 113–120.
Meseguer, P. (2012). Towards 40 years of constraint reasoning. Progress in Artificial Intelligence, 1–19. doi:10.1007/s13748-011-0006-2.
Nilsson, N. (1980). Principles of artificial intelligence. Palo Alto, CA: Tioga.
Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145–159.
Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Reading, MA: Addison-Wesley.
Pérez, E., Posada, M., & Herrera, F. (2012). Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing, 23(3), 341–356.
Reinefeld, A., & Marsland, T. A. (1994). Enhanced iterative-deepening search. IEEE Pattern Analysis and Machine Intelligence, 16(7), 701–710.
Roy, B., & Sussman, B. (1964). Les problemes d’ordonnancements avec contraintes disjonctives. Technical report, notes DS no. 9 bis, SEMA, Paris.
Sarkar, U. K., Chakrabarti, P. P., Ghose, S., & Sarkar, S. C. D. (1991). Reducing reexpansions in iterative-deepening search by controlling cutoff bounds. Artificial Intelligence, 50(2), 207–221.
Sen, A. K., & Bagchi, A. (1989). Fast recursive formulations for best-first search that allow controlled use of memory. In IJCAI, pp. 297–302.
Sierra, M. R., & Varela, R. (2010). Pruning by dominance in best-first search for the job shop scheduling problem with total flow time. Journal of Intelligent Manufacturing, 21(1), 111–119.
Smith, S. F., & Cheng, C. C. (1993). Slack-based heuristics for constraint satisfaction scheduling. In Proceedings of AAAI 1993, pp. 139–144.
Stern, R., Kulberis, T., Felner, A., & Holte, R. (2010). Using lookaheads with optimal best-first search. In AAAI.
Streeter, M. J., & Smith, S. F. (2006a). Exploiting the power of local search in a branch and bound algorithm for job shop scheduling. In Proceedings of ICAPS 2006, pp. 324–333.
Streeter, M. J., & Smith, S. F. (2006b). How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines. Journal of Artificial Intelligence Research (JAIR), 26, 247–287.
Streeter, M. J., & Smith, S. F. (2007). Using decision procedures efficiently for optimization. In Proceedings of ICAPS 2007, pp. 312–319.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285.
Taillard, E. (1994). Parallel taboo search techniques for the job shop scheduling problem. INFORMS Journal on Computing, 6(2), 108–117.
Temiz, I., & Erol, S. (2004). Fuzzy branch-and-bound for flow shop scheduling. Journal of Intelligent Manufacturing, 15, 449–454.
Van Laarhoven, P., Aarts, E., & Lenstra, K. (1992). Job shop scheduling by simulated annealing. Operations Research, 40, 113–125.
Vempaty, N. R., Kumar, V., & Korf, R. E. (1991). Depth-first versus best-first search. In AAAI, pp. 434–440.
Wah, B. W., & Shang, Y. (1994). Comparison and evaluation of a class of IDA* algorithms. International Journal of Artificial Intelligence Tools, 3(4), 493–523.
Watson, J. P., 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.
Watson, J. P., Howe, A. E., & Whitley, L. D. (2006). Deconstructing Nowicki and Smutnicki’s i-TSAB tabu search algorithm for the job-shop scheduling problem. Computers & OR, 33, 2623–2644.
Zahavi, U., Felner, A., Burch, N., & Holte, R. C. (2010). Predicting the performance of IDA* using conditional distributions. Journal of Artificial Intelligence Research (JAIR), 37, 41–83.
Zhang, C. Y., Li, P., Rao, Y., & Guan, Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & OR, 35, 282–294.
Zhou, R., & Hansen, E. A. (2006). Breadth-first heuristic search. Artificial Intelligence, 170(4–5), 385–408.
Acknowledgments
We wish to thank the anonymous referees for their useful comments that helped improving this work. We are also grateful to Mr. Neil Beckingham for his thorough work at revising the English language in this paper. This research has been supported by the Spanish Government under research project MICINN-FEDER TIN2010-20976-C02-02 and by the Principality of Asturias under grant FICYT-BP09105.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Mencía, C., Sierra, M.R. & Varela, R. Intensified iterative deepening A* with application to job shop scheduling. J Intell Manuf 25, 1245–1255 (2014). https://doi.org/10.1007/s10845-012-0726-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-012-0726-6