A robust basic cyclic scheduling problem

Idir Hamaz (), Laurent Houssin and Sonia Cafieri
Additional contact information
Idir Hamaz: LAAS-CNRS, UPS, Université de Toulouse
Laurent Houssin: LAAS-CNRS, UPS, Université de Toulouse
Sonia Cafieri: ENAC, Université de Toulouse

EURO Journal on Computational Optimization, 2018, vol. 6, issue 3, No 5, 313 pages

Abstract: 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 a budgeted uncertainty set. More precisely, we consider the uncertainty set introduced by Bertsimas and Sim (Oper Res 52(1):35–53, 2004) where the activity durations are subject to interval uncertainty and the level of robustness is controlled by a parameter. 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 a 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.

Keywords: Robust optimization; Cyclic scheduling; Dynamic programming; 90-08; 90B35; 90B36 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-018-0100-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:6:y:2018:i:3:d:10.1007_s13675-018-0100-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-018-0100-3

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().