A more efficient Lagrangian relaxation approach to job-shop scheduling problems - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , , (2)
1
2
Haoxun Chen
  • Function : Author
  • PersonId : 182315
  • IdHAL : haoxun-chen
Chengbin Chu

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.
Not file

Dates and versions

hal-02565330 , version 1 (06-05-2020)

Identifiers

Cite

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⟩

Collections

INRIA INRIA2
12 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More