Distributionally robust single machine scheduling with risk aversion

• Published in: European journal of operational research 2017-01, Vol.256 (1), p.261-274
• Main Authors: Chang, Zhiqi, Song, Shiji, Zhang, Yuli, Ding, Jian-Ya, Zhang, Rui, Chiong, Raymond
• Format: Article
• Language: English
• Subjects: Algorithms; Assignment problem; Cauchy problems; CVaR; Distributionally robust optimization; Integer programming; Job shops; Production scheduling; Risk aversion; Robustness and sensitivity analysis; Single machine scheduling; Stochastic models; Studies; Total flow time
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2016.06.025

•A first distributionally robust approach is proposed for production scheduling.•An explicit expression is provided to calculate the robust CVaR.•Three Cauchy-relaxation algorithms have been proposed to solve the problem.•Experimental results show that the proposed algorithms outperform a CPLEX solver.•Robustness of the optimal job sequence is verified via simulation experiments. This paper presents a distributionally robust (DR) optimization model for the single machine scheduling problem (SMSP) with random job processing time (JPT). To the best of our knowledge, it is the first time a DR optimization approach is applied to production scheduling problems in the literature. Unlike traditional stochastic programming models, which require an exact distribution, the presented DR-SMSP model needs only the mean-covariance information of JPT. Its aim is to find an optimal job sequence by minimizing the worst-case Conditional Value-at-Risk (Robust CVaR) of the job sequence’s total flow time. We give an explicit expression of Robust CVaR, and decompose the DR-SMSP into an assignment problem and an integer second-order cone programming (I-SOCP) problem. To efficiently solve the I-SOCP problem with uncorrelated JPT, we propose three novel Cauchy-relaxation algorithms. The effectiveness and efficiency of these algorithms are evaluated by comparing them to a CPLEX solver, and robustness of the optimal job sequence is verified via comprehensive simulation experiments. In addition, the impact of confidence levels of CVaR on the tradeoff between optimality and robustness is investigated from both theoretical and practical perspectives. Our results convincingly show that the DR-SMSP model is able to enhance the robustness of the optimal job sequence and achieve risk reduction with a small sacrifice on the optimality of the mean value. Through the simulation experiments, we have also been able to identify the strength of each of the proposed algorithms.