Dual decomposition of a single machine scheduling problem
July 1995
Article
volume 69, issue 1-3 pp 413-428.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(DualDecomposition_1995.pdf, 1.1MB) |
We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.
Keywords
Automatically Extracted Terms
- problem
- ascent direction algorithm
- algorithm
- decomposition
- direction
- lagrangian
- ascent
- precedence constraints
- programming
- constraint
- job completion times
- precedence
- value
- ascent direction
- scheduling
- velde /
- velde
- tree-optimal heuristic
- completion
- solution
