caa a22 4500 445838876 CHVBK 20180317145338.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s10951-009-0113-0 doi (NATIONALLICENCE)springer-10.1007/s10951-009-0113-0 Understanding the behavior of Solution-Guided Search forjob-shop scheduling [Elektronische Daten] [Ivan Heckman, J. Beck] This paper investigates reasons behind the behavior of constructive Solution-Guided Search (SGS) on job-shop scheduling optimization problems. In particular, two, not mutually exclusive, hypotheses are investigated: (1) Like randomized restart, SGS exploits heavy-tailed distributions of search cost; and (2) Like local search, SGS exploits search space structure such as the clustering of high-quality solutions. Theoretical and experimental evidence strongly support both hypotheses. Unexpectedly, the experiments into the second hypothesis indicate that the performance of randomized restart and standard chronological backtracking are also correlated with search space structure. This result leaves open the question of finding the mechanism by which such structure is exploited as well as suggesting a deeper connection between the performance of constructive and local search. Springer Science+Business Media, LLC, 2009 Search nationallicence Empirical analysis nationallicence Algorithm behavior nationallicence Constraint programming nationallicence Heckman Ivan Department of Computer Science, University of Toronto, Toronto, Canada aut Beck J. Department of Mechanical & Industrial Engineering, University of Toronto, Toronto, Canada aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/2(2011-04-01), 121-140 1094-6136 14:2<121 2011 14 10951 https://doi.org/10.1007/s10951-009-0113-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-009-0113-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Heckman Ivan Department of Computer Science, University of Toronto, Toronto, Canada aut NATIONALLICENCE 700 1- Beck J. Department of Mechanical & Industrial Engineering, University of Toronto, Toronto, Canada aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/2(2011-04-01), 121-140 1094-6136 14:2<121 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer