An alternative framework to Lagrangian relaxation approach for job shop scheduling

An alternative framework to Lagrangian relaxation approach for job shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor20043079
Country: Netherlands
Volume: 149
Issue: 3
Start Page Number: 499
End Page Number: 512
Publication Date: Sep 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: mathematical
Abstract:

A new Langrangian relexation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine-scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.

Reviews

Required fields are marked *. Your email address will not be published.