An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method
- 1 October 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics and Automation
- Vol. 14 (5), 786-795
- https://doi.org/10.1109/70.720354
Abstract
Concerns the use of Lagrangean relaxation for complex scheduling problems. The technique has been used to obtain near-optimal solutions for single machine and parallel machine problems. It consists of relaxing capacity constraints using Lagrange multipliers. The relaxed problem can be decomposed into independent job level subproblems. Luh et al. (1990, 1991) extended the technique to general job shop scheduling by introducing additional Lagrangean multipliers to relax precedence constraints, so that each job level relaxed subproblem can be further decomposed into a set of operation level subproblems which can easily be solved by enumeration. Unfortunately, the operation level subproblems exhibit solution oscillation from iteration to iteration and, in many cases, prevent convergence. Although several methods to prevent oscillation have been proposed, none is satisfactory. We propose an efficient pseudo-polynomial time dynamic programming algorithm. We show that, by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints becomes unnecessary, and thus the oscillation problem vanishes. This algorithm significantly improves the efficiency of the Lagrangean relaxation approach to job-shop scheduling, and makes it possible to optimize "min-max" criteria by Lagrangean relaxation. These criteria have been neglected in the Lagrangean relaxation literature due to their indecomposability. Computational results are given to demonstrate the improvements due to this algorithm.Keywords
This publication has 22 references indexed in Scilit:
- A Lagrangian relaxation approach to job shop scheduling problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling of manufacturing systems using the Lagrangian relaxation techniqueIEEE Transactions on Automatic Control, 1993
- Chapter 9 Sequencing and scheduling: Algorithms and complexityPublished by Elsevier BV ,1993
- A practical approach to job-shop scheduling problemsIEEE Transactions on Robotics and Automation, 1993
- Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due DateOperations Research, 1991
- Schedule generation and reconfiguration for parallel machinesIEEE Transactions on Robotics and Automation, 1990
- Simulated annealing for permutation flow-shop schedulingOmega, 1989
- A General Bounding Scheme for the Permutation Flow-Shop ProblemOperations Research, 1978
- Job-Shop Scheduling by Implicit EnumerationManagement Science, 1977
- A Dynamic Programming Approach to Sequencing ProblemsJournal of the Society for Industrial and Applied Mathematics, 1962