Tractable Risk Measures for the Selective Scheduling Problem with Sequence-Dependent Setup Times

Quantifying and minimizing the risk is a basic problem faced in a wide range of applications. Once the risk is explicitly quantified by a risk measure, the crucial and ambitious goal is to obtain risk-averse solutions, given the computational hurdle typically associated with opti- mization problems under risk. This is especially true for many difficult combinatorial problems, and notably for scheduling problems. This paper aims to present a few tractable risk measures for the selective scheduling problem with parallel identical machines and sequence-dependent setup times. We indicate how deterministic reformulations can be obtained when the distributional information is limited to first and second-order moment information for a broad class of risk measures. We propose an efficient heuristic for addressing the computational difficulty of the resulting models and we showcase the practical applicability of the pro- posed approach providing computational evidence on a set of benchmark instances.