IDEAS home Printed from
   My bibliography  Save this article

Distributionally robust single machine scheduling with risk aversion


  • Chang, Zhiqi
  • Song, Shiji
  • Zhang, Yuli
  • Ding, Jian-Ya
  • Zhang, Rui
  • Chiong, Raymond


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.

Suggested Citation

  • Chang, Zhiqi & Song, Shiji & Zhang, Yuli & Ding, Jian-Ya & Zhang, Rui & Chiong, Raymond, 2017. "Distributionally robust single machine scheduling with risk aversion," European Journal of Operational Research, Elsevier, vol. 256(1), pages 261-274.
  • Handle: RePEc:eee:ejores:v:256:y:2017:i:1:p:261-274
    DOI: 10.1016/j.ejor.2016.06.025

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Wu, Xianyi & Zhou, Xian, 2008. "Stochastic scheduling to minimize expected maximum lateness," European Journal of Operational Research, Elsevier, vol. 190(1), pages 103-115, October.
    2. Hua Sun & Ziyou Gao & W. Szeto & Jiancheng Long & Fangxia Zhao, 2014. "A Distributionally Robust Joint Chance Constrained Optimization Model for the Dynamic Network Design Problem under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 14(3), pages 409-433, December.
    3. S. Liao & Christian van Delft & J.-P. Vial, 2013. "Distributionally robust workforce scheduling in call centres with uncertain arrival rates," Post-Print hal-01069123, HAL.
    4. Jang, Wooseung, 2002. "Dynamic scheduling of stochastic jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 138(3), pages 518-530, May.
    5. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    6. Soroush, H.M., 2007. "Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 181(1), pages 266-287, August.
    7. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    8. Koulamas, Christos, 2010. "The single-machine total tardiness scheduling problem: Review and extensions," European Journal of Operational Research, Elsevier, vol. 202(1), pages 1-7, April.
    9. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    10. Lo, Andrew W., 1987. "Semi-parametric upper bounds for option prices and expected payoffs," Journal of Financial Economics, Elsevier, vol. 19(2), pages 373-387, December.
    11. De, Prabuddha & Ghosh, Jay B. & Wells, Charles E., 1992. "Expectation-variance analyss of job sequences under processing time uncertainty," International Journal of Production Economics, Elsevier, vol. 28(3), pages 289-297, December.
    12. Nguyen, Tri-Dung & Lo, Andrew W., 2012. "Robust ranking and portfolio optimization," European Journal of Operational Research, Elsevier, vol. 221(2), pages 407-416.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Chang, Zhiqi & Ding, Jian-Ya & Song, Shiji, 2019. "Distributionally robust scheduling on parallel machines under moment uncertainty," European Journal of Operational Research, Elsevier, vol. 272(3), pages 832-846.
    2. Carlo Meloni & Marco Pranzo, 2020. "Expected shortfall for the makespan in activity networks under imperfect information," Flexible Services and Manufacturing Journal, Springer, vol. 32(3), pages 668-692, September.
    3. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    4. Qiu, Rui & Xu, Jiuping & Ke, Ruimin & Zeng, Ziqiang & Wang, Yinhai, 2020. "Carbon pricing initiatives-based bi-level pollution routing problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 203-217.
    5. Chen, J.J. & Zhao, Y.L. & Peng, K. & Wu, P.Z., 2017. "Optimal trade-off planning for wind-solar power day-ahead scheduling under uncertainties," Energy, Elsevier, vol. 141(C), pages 1969-1981.


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:256:y:2017:i:1:p:261-274. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Haili He). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.