{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T06:56:08Z","timestamp":1763016968397},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,8,5]],"date-time":"2009-08-05T00:00:00Z","timestamp":1249430400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s10951-009-0113-0","type":"journal-article","created":{"date-parts":[[2009,8,4]],"date-time":"2009-08-04T11:33:30Z","timestamp":1249385610000},"page":"121-140","source":"Crossref","is-referenced-by-count":1,"title":["Understanding the behavior of Solution-Guided Search for\u00a0job-shop scheduling"],"prefix":"10.1007","volume":"14","author":[{"given":"Ivan","family":"Heckman","sequence":"first","affiliation":[]},{"given":"J. Christopher","family":"Beck","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,5]]},"reference":[{"key":"113_CR1","unstructured":"Achlioptas, D., Gomes, C. P., Kautz, H. A., & Selman, B. (2000). Generating satisfiable problem instances. In Proceedings of the seventeenth national conference on artificial intelligence (pp.\u00a0256\u2013261)."},{"key":"113_CR2","doi-asserted-by":"crossref","unstructured":"Baptista, L., & Silva, J. P. M. (2000). Using randomization and learning to solve hard real-world instances of satisfiability. In Principles and practice of constraint programming (pp.\u00a0489\u2013494).","DOI":"10.1007\/3-540-45349-0_36"},{"key":"113_CR3","unstructured":"Beck, J. C. (1999). Texture measurements as a basis for heuristic commitment techniques in constraint-directed scheduling. PhD thesis, University of Toronto."},{"key":"113_CR4","doi-asserted-by":"crossref","unstructured":"Beck, J. C. (2005). Multi-point constructive search. In Proceedings of the eleventh international conference on principles and practice of constraint programming (CP\u201905) (pp.\u00a0737\u2013741).","DOI":"10.1007\/11564751_55"},{"key":"113_CR5","unstructured":"Beck, J. C. (2005). Multi-point constructive search: Extended remix. In Proceedings of the CP2005 workshop on local search techniques for constraint satisfaction (pp.\u00a017\u201331)."},{"key":"113_CR6","unstructured":"Beck, J. C. (2006). An empirical study of multi-point constructive search for constraint-based scheduling. In Proceedings of the sixteenth international on automated planning and scheduling (ICAPS06) (pp.\u00a0274\u2013283)."},{"key":"113_CR7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1613\/jair.2169","volume":"29","author":"J. C. Beck","year":"2007","unstructured":"Beck, J. C. (2007). Solution-guided multi-point constructive search for job shop scheduling. Journal of Artificial Intelligence Research, 29, 49\u201377.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"113_CR8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0004-3702(99)00099-5","volume":"117","author":"J. C. Beck","year":"2000","unstructured":"Beck, J. C., & Fox, M. S. (2000). Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics. Artificial Intelligence, 117(1), 31\u201381.","journal-title":"Artificial Intelligence"},{"key":"113_CR9","unstructured":"Beck, J. C., & Watson, J.-P. (2003). Adaptive search algorithms and fitness-distance correlation. In Proceedings of the fifth metaheuristics international conference."},{"issue":"1","key":"113_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0377-2217(95)00362-2","volume":"93","author":"J. Blazewicz","year":"1996","unstructured":"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\u201333.","journal-title":"European Journal of Operational Research"},{"key":"113_CR11","first-page":"408","volume-title":"CP\u201901: Proceedings of the 7th international conference on principles and practice of constraint programming","author":"H. Chen","year":"2001","unstructured":"Chen, H., Gomes, C. P., & Selman, B. (2001). Formal models of heavy-tailed behavior in combinatorial search. In CP\u201901: Proceedings of the 7th international conference on principles and practice of constraint programming (pp. 408\u2013421). London: Springer."},{"key":"113_CR12","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-61551-2_70","volume-title":"Proceedings of the second international conference on principles and practice of constraint programming (CP\u201996)","author":"D. A. Clark","year":"1996","unstructured":"Clark, D. A., Frank, J., Gent, I. P., MacIntyre, E., Tomov, N., & Walsh, T. (1996). Local search and the number of solutions. In Proceedings of the second international conference on principles and practice of constraint programming (CP\u201996) (pp. 119\u2013133). Berlin: Springer."},{"key":"113_CR13","unstructured":"Gent, I. P., MacIntyre, E., Prosser, P., & Walsh, T. (1996). The constrainedness of search. In Proceedings of the thirteenth national conference on artificial intelligence (AAAI-96) (Vol.\u00a01, pp.\u00a0246\u2013252)."},{"key":"113_CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1109\/TAI.1999.809823","volume-title":"Proceedings of the 11th IEEE international conference on tools with artificial intelligence","author":"C. P. Gomes","year":"1999","unstructured":"Gomes, C. P., & Selman, B. (1999). Search strategies for hybrid search spaces. In Proceedings of the 11th IEEE international conference on tools with artificial intelligence (p. 359). Los Alamitos: IEEE Computer Society."},{"key":"113_CR15","unstructured":"Gomes, C. P., Selman, B., & Kautz, H. (1998). Boosting combinatorial search through randomization. In Proceedings of the fifteenth national conference on artificial intelligence (AAAI-98) (pp.\u00a0431\u2013437)."},{"issue":"1\/2","key":"113_CR16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","volume":"24","author":"C. P. Gomes","year":"2000","unstructured":"Gomes, C. P., Selman, B., Crato, N., & Kautz, H. A. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, 24(1\/2), 67\u2013100.","journal-title":"Journal of Automated Reasoning"},{"key":"113_CR17","doi-asserted-by":"crossref","unstructured":"Gomes, C. P., Fern\u00e0ndes, C., Selman, B., & Bessiere, C. (2004). Statistical regimes across constrainedness regions. In Proceedings of the tenth international conference on the principles and practice of constraint programming (CP2004) (pp.\u00a032\u201346).","DOI":"10.1007\/978-3-540-30201-8_6"},{"issue":"4","key":"113_CR18","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10601-005-2807-z","volume":"10","author":"C. P. Gomes","year":"2005","unstructured":"Gomes, C. P., Fern\u00e1ndez, C., Selman, B., & Bessi\u00e8re, C. (2005). Statistical regimes across constrainedness regions. Constraints, 10(4), 317\u2013337.","journal-title":"Constraints"},{"key":"113_CR19","unstructured":"Heckman, I. (2007). Empirical analysis of solution guided multi-point constructive search. Master\u2019s thesis, Department of Computer Science, University of Toronto."},{"key":"113_CR20","first-page":"112","volume-title":"Proceedings of the fourth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR\u201907)","author":"I. Heckman","year":"2007","unstructured":"Heckman, I., & Beck, J. C. (2007). Fitness-distance correlation and solution-guided multi-point constructive search. In L. Perron & M. Trick (Eds.), Proceedings of the fourth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR\u201907) (pp. 112\u2013126). Berlin: Springer."},{"key":"113_CR21","first-page":"184","volume-title":"Proceedings of the sixth international conference on genetic algorithms","author":"T. Jones","year":"1995","unstructured":"Jones, T., & Forrest, S. (1995). Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In L. Eshelman (Ed.), Proceedings of the sixth international conference on genetic algorithms (pp. 184\u2013192). San Francisco: Morgan Kaufmann."},{"issue":"1","key":"113_CR22","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1287\/opre.40.1.113","volume":"40","author":"P. J. M. Laarhoven","year":"1992","unstructured":"Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992). Job shop scheduling by simulated annealing. Operations Research, 40(1), 113\u2013125.","journal-title":"Operations Research"},{"key":"113_CR23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0004-3702(02)00362-4","volume":"143","author":"P. Laborie","year":"2003","unstructured":"Laborie, P. (2003). Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence, 143, 151\u2013188.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"113_CR24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1049\/ise.1994.0009","volume":"3","author":"C. Le Pape","year":"1994","unstructured":"Le Pape, C. (1994). Implementation of resource constraints in ILOG Schedule: A library for the development of constraint-based scheduling systems. Intelligent Systems Engineering, 3(2), 55\u201366.","journal-title":"Intelligent Systems Engineering"},{"key":"113_CR25","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(93)90029-9","volume":"47","author":"M. Luby","year":"1993","unstructured":"Luby, M., Sinclair, A., & Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47, 173\u2013180.","journal-title":"Information Processing Letters"},{"key":"113_CR26","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1023\/A:1018979424002","volume":"86","author":"D. C. Mattfeld","year":"1999","unstructured":"Mattfeld, D. C., Bierwirth, C., & Kopfer, H. (1999). A search space analysis of the job shop scheduling problem. Annals of Operations Research, 86, 441\u2013453.","journal-title":"Annals of Operations Research"},{"key":"113_CR27","unstructured":"Mitchell, D., Selman, B., & Levesque, H. (1992). Hard and easy distributions of SAT problems. In Proceedings of the tenth national conference on artificial intelligence (AAAI-92) (pp.\u00a0459\u2013465)."},{"key":"113_CR28","unstructured":"Nuijten, W. P. M. (1994). Time and resource constrained scheduling: a constraint satisfaction approach. PhD thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology."},{"key":"113_CR29","unstructured":"Parkes, A. J. (1997). Clustering at the phase transition. In Proceedings of the fourteenth national conference on artificial intelligence (AAAI-97) (pp.\u00a0340\u2013345). Providence, RI."},{"key":"113_CR30","unstructured":"Scheduler (2006). ILOG Scheduler 6.2 User\u2019s manual and reference manual. ILOG, S.A."},{"key":"113_CR31","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1613\/jair.711","volume":"12","author":"J. Singer","year":"2000","unstructured":"Singer, J., Gent, I. P., & Smaill, A. (2000). Backbone fragility and local search cost peak. Journal of Artificial Intelligence Research, 12, 235\u2013270.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"113_CR32","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B. M. Smith","year":"1996","unstructured":"Smith, B. M., & Dyer, M. E. (1996). Locating the phase transition in constraint satisfaction problems. Artificial Intelligence, 81, 155\u2013181.","journal-title":"Artificial Intelligence"},{"key":"113_CR33","unstructured":"Watson, J.-P. (2003). Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. PhD thesis, Dept. of Computer Science, Colorado State University."},{"key":"113_CR34","doi-asserted-by":"crossref","unstructured":"Watson, J.-P., & Beck, J. C. (2008). A hybrid constraint programming\/local search approach to the job-shop scheduling problem. In Proceedings of the fifth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR\u201908) (pp.\u00a0263\u2013277).","DOI":"10.1007\/978-3-540-68155-7_21"},{"issue":"2","key":"113_CR35","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1287\/ijoc.14.2.98.120","volume":"14","author":"J.-P. Watson","year":"2002","unstructured":"Watson, J.-P., Barbulescu, L., Whitley, L. D., & Howe, A. E. (2002). Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance. INFORMS Journal on Computing, 14(2), 98\u2013123.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"113_CR36","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0004-3702(02)00363-6","volume":"143","author":"J.-P. Watson","year":"2003","unstructured":"Watson, J.-P., Beck, J. C., Howe, A. E., & Whitley, L. D. (2003). Problem difficulty for tabu search in job-shop scheduling. Artificial Intelligence, 143(2), 189\u2013217.","journal-title":"Artificial Intelligence"},{"key":"113_CR37","unstructured":"Williams, R., Gomes, C., & Selman, B. (2003). On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Proceedings of sixth international conference on theory and applications of satisfiability testing (SAT-03)."},{"key":"113_CR38","doi-asserted-by":"crossref","unstructured":"Wu, H., & van Beek, P. (2007). On universal restart strategies for backtracking search. In Proceedings of the thirteenth international conference on the principles and practice of constraint programming (CP 2007) (pp.\u00a0681\u2013695).","DOI":"10.1007\/978-3-540-74970-7_48"},{"key":"113_CR39","doi-asserted-by":"crossref","unstructured":"Yokoo, M. (1997). Why adding more constraints makes a problem easier for hill-climbing algorithms: Analyzing landscapes of CSPs. In Principles and practice of constraint programming (pp.\u00a0356\u2013370).","DOI":"10.1007\/BFb0017451"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0113-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-009-0113-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-009-0113-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T05:39:42Z","timestamp":1559453982000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-009-0113-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,5]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["113"],"URL":"https:\/\/doi.org\/10.1007\/s10951-009-0113-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,5]]}}}