Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems

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 follow...

Full description

Saved in:
Bibliographic Details
Published in:IIE transactions 1998-11, Vol.30 (11), p.1085-1097
Main Authors: KASKAVELIS, CHRISTOS A., CARAMANIS, MICHAEL C.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Costs
Employment
Exact sciences and technology
Heuristic
Integer programming
Job shops
Lagrange multiplier
Linear programming
Methods
Operational research and scientific management
Operational research. Management science
Schedules
Scheduling
Scheduling, sequencing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0740-817X
2472-5854
1545-8830
2472-5862
DOI:10.1080/07408179808966565