IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i6p3059-3079.html
   My bibliography  Save this article

Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms

Author

Listed:
  • Guopeng Song

    (College of Systems Engineering, National University of Defense Technology, 410073 Changsha, China)

  • Roel Leus

    (Research Centre for Operations Research and Statistics (ORSTAT), Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium)

Abstract

We study parallel machine scheduling for makespan minimization with uncertain job processing times. To incorporate uncertainty and generate solutions that are, in some way, insensitive to unfolding information, three different modeling paradigms are adopted: a robust model, a chance-constrained model, and a distributionally robust chance-constrained model. We focus on devising generic solution methods that can efficiently handle these different models. We develop two general solution procedures: a cutting-plane method that leverages the submodularity in the models and a customized dichotomic search procedure with a decision version of a bin packing variant under uncertainty solved in each iteration. A branch-and-price algorithm is designed to solve the bin packing problems. The efficiency of our methods is shown through extensive computational tests. We compare the solutions from the different models and report the general lessons learned regarding the choice between different frameworks for planning under uncertainty.

Suggested Citation

  • Guopeng Song & Roel Leus, 2022. "Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3059-3079, November.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:6:p:3059-3079
    DOI: 10.1287/ijoc.2022.1229
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1229
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1229?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Christian Tjandraatmadja & Willem-Jan van Hoeve, 2019. "Target Cuts from Relaxed Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 285-301, April.
    2. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    3. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    4. David Bergman & Andre A. Cire & Willem-Jan van Hoeve & J. N. Hooker, 2016. "Discrete Optimization with Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 47-66, February.
    5. Maxime C. Cohen & Philipp W. Keller & Vahab Mirrokni & Morteza Zadimoghaddam, 2019. "Overcommitment in Cloud Services: Bin Packing with Chance Constraints," Management Science, INFORMS, vol. 65(7), pages 3255-3271, July.
    6. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    7. Laurent El Ghaoui & Maksim Oks & Francois Oustry, 2003. "Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach," Operations Research, INFORMS, vol. 51(4), pages 543-556, August.
    8. Wolfram Wiesemann & Daniel Kuhn & Melvyn Sim, 2014. "Distributionally Robust Convex Optimization," Operations Research, INFORMS, vol. 62(6), pages 1358-1376, December.
    9. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    10. Dimitris Bertsimas & Xuan Vinh Doan & Karthik Natarajan & Chung-Piaw Teo, 2010. "Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 580-602, August.
    11. Mula, J. & Poler, R. & Garcia-Sabater, J.P. & Lario, F.C., 2006. "Models for production planning under uncertainty: A review," International Journal of Production Economics, Elsevier, vol. 103(1), pages 271-285, September.
    12. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    13. Michael Pinedo, 1983. "Stochastic Scheduling with Release Dates and Due Dates," Operations Research, INFORMS, vol. 31(3), pages 559-572, June.
    14. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    15. 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.
    16. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    17. Mokotoff, Ethel, 2004. "An exact algorithm for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 152(3), pages 758-769, February.
    18. Dimitris Bertsimas & Aurélie Thiele, 2006. "A Robust Optimization Approach to Inventory Theory," Operations Research, INFORMS, vol. 54(1), pages 150-168, February.
    19. Daniel Kowalczyk & Roel Leus, 2017. "An exact algorithm for parallel machine scheduling with conflicts," Journal of Scheduling, Springer, vol. 20(4), pages 355-372, August.
    20. 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.
    21. Zheng Zhang & Brian T. Denton & Xiaolan Xie, 2020. "Branch and Price for Chance-Constrained Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 547-564, July.
    22. Mauro Dell'Amico & Manuel Iori & Silvano Martello & Michele Monaci, 2008. "Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 333-344, August.
    23. Letsios, Dimitrios & Mistry, Miten & Misener, Ruth, 2021. "Exact lexicographic scheduling and approximate rescheduling," European Journal of Operational Research, Elsevier, vol. 290(2), pages 469-478.
    24. Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
    25. James E. Smith & Robert L. Winkler, 2006. "The Optimizer's Curse: Skepticism and Postdecision Surprise in Decision Analysis," Management Science, INFORMS, vol. 52(3), pages 311-322, March.
    26. Mauro Dell’Amico & Silvano Martello, 1995. "Optimal Scheduling of Tasks on Identical Parallel Processors," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 191-200, May.
    27. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    28. Dell'Amico, Mauro & Martello, Silvano, 2005. "A note on exact algorithms for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 160(2), pages 576-578, January.
    29. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    30. Grani A. Hanasusanto & Vladimir Roitch & Daniel Kuhn & Wolfram Wiesemann, 2017. "Ambiguous Joint Chance Constraints Under Mean and Dispersion Information," Operations Research, INFORMS, vol. 65(3), pages 751-767, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    2. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    3. Lu, Mengshi & Nakao, Hideaki & Shen, Siqian & Zhao, Lin, 2021. "Non-profit resource allocation and service scheduling with cross-subsidization and uncertain resource consumptions," Omega, Elsevier, vol. 99(C).
    4. Zhi Chen & Melvyn Sim & Peng Xiong, 2020. "Robust Stochastic Optimization Made Easy with RSOME," Management Science, INFORMS, vol. 66(8), pages 3329-3339, August.
    5. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    6. Georgia Perakis & Melvyn Sim & Qinshen Tang & Peng Xiong, 2023. "Robust Pricing and Production with Information Partitioning and Adaptation," Management Science, INFORMS, vol. 69(3), pages 1398-1419, March.
    7. Jun Li & Yizhe Huang & Yan‐Fu Li & Shuming Wang, 2023. "Redundancy allocation under state‐dependent distributional uncertainty of component lifetimes," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 930-950, March.
    8. Grani A. Hanasusanto & Vladimir Roitch & Daniel Kuhn & Wolfram Wiesemann, 2017. "Ambiguous Joint Chance Constraints Under Mean and Dispersion Information," Operations Research, INFORMS, vol. 65(3), pages 751-767, June.
    9. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    10. 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.
    11. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    12. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    13. Amir Ardestani-Jaafari & Erick Delage, 2016. "Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems," Operations Research, INFORMS, vol. 64(2), pages 474-494, April.
    14. Liu, Kanglin & Li, Qiaofeng & Zhang, Zhi-Hai, 2019. "Distributionally robust optimization of an emergency medical service station location and sizing problem with joint chance constraints," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 79-101.
    15. Kris Boudt & Edgars Jakobsons & Steven Vanduffel, 2018. "Block rearranging elements within matrix columns to minimize the variability of the row sums," 4OR, Springer, vol. 16(1), pages 31-50, March.
    16. Mengshi Lu & Zuo‐Jun Max Shen, 2021. "A Review of Robust Operations Management under Model Uncertainty," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1927-1943, June.
    17. Yue Zhao & Zhi Chen & Zhenzhen Zhang, 2023. "Distributionally Robust Chance-Constrained p -Hub Center Problem," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1361-1382, November.
    18. Shunichi Ohmori, 2021. "A Predictive Prescription Using Minimum Volume k -Nearest Neighbor Enclosing Ellipsoid and Robust Optimization," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    19. Antonio J. Conejo & Nicholas G. Hall & Daniel Zhuoyu Long & Runhao Zhang, 2021. "Robust Capacity Planning for Project Management," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1533-1550, October.
    20. Meysam Cheramin & Jianqiang Cheng & Ruiwei Jiang & Kai Pan, 2022. "Computationally Efficient Approximations for Distributionally Robust Optimization Under Moment and Wasserstein Ambiguity," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1768-1794, May.

    Corrections

    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:inm:orijoc:v:34:y:2022:i:6:p:3059-3079. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.