Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems
作者:
CHRISTOSA. KASKAVELIS,
MICHAELC. CARAMANIS,
期刊:
IIE Transactions
(Taylor Available online 1998)
卷期:
Volume 30,
issue 11
页码: 1085-1097
ISSN:0740-817X
年代: 1998
DOI:10.1080/07408179808966565
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
We improve the job specific decomposition Lagrangian relaxation algorithm applied to industry size job shop scheduling problems with more than 10 000 resource constraints. We introduce two new features in the Lagrange multiplier updating procedure. First, the usual solution of all subproblems followed by dual cost estimation and update of multiplier values is replaced by the estimation of a surrogate dual cost function and a more frequent update of multipliers is implemented after each subproblem solution. Second, an adaptive step size in the subgradient based multiplier update is introduced. Asymptotic properties of the surrogate dual cost function are obtained and the proposed algorithmic improvements are evaluated in extensive numerical examples including published data used by other researchers, as well as extensive real industrial scheduling system data.
点击下载:
PDF (1822KB)
返 回