Minimizing conditional-value-at-risk for stochastic scheduling problems

This paper introduces the use of conditional-value-at-risk (CVaR) as a criterion for stochastic scheduling problems. This criterion has the tendency of simultaneously reducing both the expectation and variance of a performance measure, while retaining linearity whenever the expectation can be represented by a linear expression. In this regard, it offers an added advantage over traditional nonlinear expectation-variance-based approaches. We begin by formulating a scenario-based mixed-integer program formulation for minimizing CVaR for general scheduling problems. We then demonstrate its application for the single machine total weighted tardiness problem, for which we present both a specialized l-shaped algorithm and a dynamic programming-based heuristic procedure. Our numerical experimental results reveal the benefits and effectiveness of using the CVaR criterion. Likewise, we also exhibit the use and effectiveness of minimizing CVaR in the context of the parallel machine total weighted tardiness problem. We believe that minimizing CVaR is an effective approach and holds great promise for achieving risk-averse solutions for stochastic scheduling problems that arise in diverse practical applications.