Skip to Main content Skip to Navigation
Journal articles

On the exact solution of a large class of parallel machine scheduling problems

Teobaldo Bulhoes 1 Ruslan Sadykov 2 Anand Subramanian 1 Eduardo Uchoa 3
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 work deals with a very generic class of scheduling problems with identical/uniform/unrelated parallel machine environment. It considers well-known attributes such as release dates or sequence-dependent setup times and accepts any objective function defined over job completion times. Non-regular objectives are also supported. We introduce a branch-cut-and-price algorithm for such problems that makes use of non-robust cuts, i.e., cuts which change the structure of the pricing problem. This is the first time that such cuts are employed for machine scheduling problems. The algorithm also embeds other important techniques such as strong branching, reduced cost fixing and dual stabilization. Computational experiments over literature benchmarks showed that the proposed algorithm is indeed effective and could solve many instances to optimality for the first time.
Document type :
Journal articles
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-01958180
Contributor : Ruslan Sadykov <>
Submitted on : Monday, December 17, 2018 - 5:35:34 PM
Last modification on : Saturday, February 13, 2021 - 3:21:47 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Teobaldo Bulhoes, Ruslan Sadykov, Anand Subramanian, Eduardo Uchoa. On the exact solution of a large class of parallel machine scheduling problems. Journal of Scheduling, Springer Verlag, 2020, 23, pp.411-429. ⟨10.1007/s10951-020-00640-z⟩. ⟨hal-01958180⟩

Share

Metrics

Record views

150

Files downloads

376