Robust Basic Cyclic Scheduling Problem

Abstract : This paper addresses the Basic Cyclic Scheduling Problem where the processing times are affected by uncertainties. We formulate the problem as a two-stage robust optimization problem with polyhedral uncertainty set. We propose three exact algorithms for solving the problem. Two of them use a negative circuit detection algorithm as a subroutine and the last one is an Howard's algorithm adaptation. Results of numerical experiments on randomly generated instances show that the Howard's algorithm adaptation yields efficient results and opens perspectives on more difficult robust cyclic scheduling problems.
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01635856
Contributor : Idir Hamaz <>
Submitted on : Wednesday, November 15, 2017 - 5:54:17 PM
Last modification on : Tuesday, February 11, 2020 - 1:55:42 PM
Long-term archiving on: Friday, February 16, 2018 - 3:40:22 PM

File

robust-basic-cyclic-problem.pd...
Files produced by the author(s)

Identifiers

Citation

Idir Hamaz, Laurent Houssin, Sonia Cafieri. Robust Basic Cyclic Scheduling Problem. EURO Journal on Computational Optimization, Springer, 2018, 6 (3), pp.291-313. ⟨10.1007/s13675-018-0100-3⟩. ⟨hal-01635856⟩

Share

Metrics

Record views

284

Files downloads

388