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

Quantifying and minimizing the risk is a basic problem facedin a wide range of applications. Once the risk is explicitly quantified bya risk measure, the crucial and ambitious goal is to obtain risk-aversesolutions, given the computational hurdle typically associated with opti-mization problems under risk. This is especially true for many difficultcombinatorial problems, and notably for scheduling problems. This paperaims to present a few tractable risk measures for the selective schedulingproblem with parallel identical machines and sequence-dependent setuptimes. We indicate how deterministic reformulations can be obtainedwhen the distributional information is limited to first and second-ordermoment information for a broad class of risk measures. We proposean efficient heuristic for addressing the computational difficulty of theresulting models and we showcase the practical applicability of the pro-posed approach providing computational evidence on a set of benchmarkinstances.