Understanding the behavior of Solution-Guided Search for聽job-shop scheduling
| 详细信息 | 推荐本文 | |
- 作者：Ivan Heckman (1) iheckman@gmail.com
J. Christopher Beck (2) jcb@mie.utoronto.ca - 关键词：Search – ; Empirical analysis – ; Algorithm behavior – ; Constraint programming
- 刊名：Journal of Scheduling
- 出版时间：April 2011
- 出版年：2011
- 期刊代码：94_1094-6136
- 类别：cp
- 卷：14
- 期：2
- 页码：121-140
- 数据来源：sp
摘要
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.