A new Lagrangian bound for the min-sum job-shop scheduling

Shunji Tanaka 1 Ruslan Sadykov 2, * Boris Detienne 3, 2
* Corresponding author
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : This study will propose a new Lagrangian bound for the min-sum job-shop scheduling problem. The proposed method is an integration of two types of Lagrangian relaxation methods known as job-level and machine-level decomposition methods. It will be shown by numerical experiments that the proposed method can improve the existing lower bounds significantly.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01248322
Contributor : Ruslan Sadykov <>
Submitted on : Thursday, December 24, 2015 - 6:17:33 PM
Last modification on : Monday, November 26, 2018 - 4:12:03 PM

File

Tanaka_etall_ISS15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01248322, version 1

Citation

Shunji Tanaka, Ruslan Sadykov, Boris Detienne. A new Lagrangian bound for the min-sum job-shop scheduling. International Symposium on Scheduling ISS'2015, Jul 2015, Kobe, Japan. ⟨hal-01248322⟩

Share

Metrics

Record views

301

Files downloads

138