Name
Title | ||
|---|---|---|
Looking for Shortcuts: Infeasible Search Analysis for Oversubscribed Scheduling Problems |
Abstract | ||
|---|---|---|
Searches that include both feasible and infeasible solu- tions have proved to be efficient algorithms for solv- ing some scheduling problems. Researchers conjec- ture that these algorithms yield two primary benefits: 1) they tend to focus on solutions close to the bound- ary between feasible and infeasible solutions, where active constraints are likely to yield optimal values, and 2) moves that include infeasible solutions may un- cover short-cuts in a search space. Researchers have published empirical studies that confirm the value of searching along the feasible-infeasible boundary, but until now there has been little direct evidence that in- feasible search yields short-cuts. We present empirical results in two oversubscribed scheduling domains for which boundary region search in infeasible space appears to offer advantages over search in strictly feasible space. Our results confirm that infeasible search finds shortcuts that may improve search efficiency more than boundary region search alone. However, our results also reveal that ineffi- cient infeasible paths which we call detours may de- grade search performance, potentially offsetting effi- ciency shortcuts may provide. |
Year | Venue | Keywords |
|---|---|---|
2006 | ICAPS | empirical study,search space,scheduling problem |
Field | DocType | Citations |
Mathematical optimization,Computer science,Scheduling (computing),Beam search,Conjecture,Empirical research | Conference | 1 |
PageRank | References | Authors |
0.37 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark F. Rogers | 1 | 32 | 5.38 |
| Adele E. Howe | 2 | 561 | 65.70 |
| L. Darrell Whitley | 3 | 6631 | 968.30 |