Skip to Main content Skip to Navigation

Job Shop Using Lagrangian Relaxation

Abstract : Lagrangian relaxation has recently emerged as an important method for solving complex scheduling problems. The technique has succeesfully been used to obtain near-optimal solutions for one machine scheduling problems and parallel machine scheduling problems. The approach consists of relaxing the capacity constraints on machines by using Lagrangian multipliers. The relaxed problem can be decomposed into independent job level subproblems. Peter B. Luh and his colleagues extended the technique to general job shop scheduling problems by introducing more Lagrangian multipliers to relax the precedence constraints among operations. Such 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 of the algorithm. Although they have proposed several method to prevent solution from oscillation, none of the methods is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to relaxed job level subproblems. We show that by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints is un-necessary, and thus the oscillation problem vanishes. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Furthermore, this algorithm makes it possible to optimize "min-max" criteria by Lagrangian relaxation. These criteria have been neglected in Lagrangian relaxation litterature for sake of indecomposability. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:40:10 PM
Last modification on : Friday, February 4, 2022 - 3:23:44 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 3:41:39 PM


  • HAL Id : inria-00074173, version 1



Haoxun Chen, Chengbin Chu, Jean-Marie Proth. Job Shop Using Lagrangian Relaxation. [Research Report] RR-2505, INRIA. 1995, pp.15. ⟨inria-00074173⟩



Record views


Files downloads