Name
Abstract | ||
|---|---|---|
Constraint logic programming has been applied to cost minimization problems such as job-shop scheduling with some success, using the (depth-first) branch and bound method. Recent work has shown that problem-specific heuristics can improve the performance of CLP systems on combinatorial optimisation problems. In this paper we take an orthogonal approach, by developing a generic parallel branch and bound strategy which improves existing CLP strategies in several ways: by avoiding the sometimes prohibitive overheads common to existing implementations; by speeding up convergence to optimal solutions; and by speeding up the proof of optimality for suboptimal solutions. The latter two improvements exploit parallelism in novel ways, which can be smoothly integrated with Or-parallelism. We evaluate these ideas on a set of job-shop scheduling problems, in some cases achieving order of magnitude speedups. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-60299-2_32 | CP |
Keywords | Field | DocType |
improved branch,constraint logic programming,branch and bound,job shop scheduling | Branch and bound,Mathematical optimization,Job shop scheduling,Computer science,Branch and price,Branch and cut,Flow shop scheduling,Heuristics,Concurrent constraint logic programming,Constraint logic programming | Conference |
ISBN | Citations | PageRank |
3-540-60299-2 | 4 | 0.49 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steven David Prestwich | 1 | 608 | 47.15 |
| Shyam Mudambi | 2 | 69 | 6.20 |