Skip to Main content Skip to Navigation
Conference papers

A more efficient Lagrangian relaxation approach to job-shop scheduling problems

Abstract : Lagrangian relaxation consists of relaxing capacity constraints using Lagrangian multipliers and of decomposing the problem into job level subproblems. In the literature, when job shop scheduling problems are considered, these subproblems are further decomposed into operation level subproblems by relaxing precedence constraints. Unfortunately, this results in solution oscillation and often prevents convergence of the algorithm. Although several methods have been proposed to avoid solution oscillation, none of them is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to solve relaxed job level subproblems. This makes the relaxation of precedence constraints unnecessary. The solution oscillation can then be avoided. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02565330
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Wednesday, May 6, 2020 - 1:05:04 PM
Last modification on : Wednesday, June 10, 2020 - 10:00:04 AM

Identifiers

Collections

Citation

Haoxun Chen, Chengbin Chu, Jean-Marie Proth. A more efficient Lagrangian relaxation approach to job-shop scheduling problems. 1995 IEEE International Conference on Robotics and Automation, May 1995, Nagoya, Japan. pp.496-501, ⟨10.1109/ROBOT.1995.525332⟩. ⟨hal-02565330⟩

Share

Metrics

Record views

19