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.