IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v316y2024i3p856-872.html
   My bibliography  Save this article

A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs

Author

Listed:
  • Chen, Jianfu
  • Chu, Chengbin
  • Sahli, Abderrahim
  • Li, Kai

Abstract

This paper considers unrelated parallel machine scheduling involving machine usage costs, in addition to classic job completion time-related costs. The usage cost of each machine is made up of a fixed usage cost and a variable usage cost proportional to the total processing time of the jobs assigned to it. These features model many practical situations where machine usage costs include, for example, rental fees when the machines are not owned but rented. To tackle this problem, four mathematical models based on the Shortest Weighted Processing Time (SWPT) rule are introduced. Additionally, the problem is formulated into a set-partitioning model, for which a branch-and-price algorithm is proposed with an appropriate branching strategy. This facilitates the development of an efficient pseudo-polynomial dynamic programming algorithm and a polynomial-time heuristic to solve the pricing problem. Extensive numerical experiments demonstrate the superior performance of the proposed branch-and-price algorithm over the four SWPT-based mathematical formulations and an existing branch-and-price algorithm designed for a special case. Notably, it can optimally solve instances involving up to 225 jobs and 15 machines within one hour. Moreover, statistical analyses reveal that the proposed polynomial-time heuristic significantly reduces the computation time, and the mathematical model based on the contribution of every job to the total weighted completion time exhibits the best overall performance.

Suggested Citation

  • Chen, Jianfu & Chu, Chengbin & Sahli, Abderrahim & Li, Kai, 2024. "A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs," European Journal of Operational Research, Elsevier, vol. 316(3), pages 856-872.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:3:p:856-872
    DOI: 10.1016/j.ejor.2024.03.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724001851
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.03.011?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
    ---><---

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

    References listed on IDEAS

    as
    1. Jiang, Xiaojuan & Lee, Kangbok & Pinedo, Michael L., 2021. "Ideal schedules in parallel machine settings," European Journal of Operational Research, Elsevier, vol. 290(2), pages 422-434.
    2. Weng, Michael X. & Lu, John & Ren, Haiying, 2001. "Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective," International Journal of Production Economics, Elsevier, vol. 70(3), pages 215-226, April.
    3. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    4. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    5. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    6. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    7. Fei, H. & Chu, C. & Meskens, N. & Artiba, A., 2008. "Solving surgical cases assignment problem by a branch-and-price approach," International Journal of Production Economics, Elsevier, vol. 112(1), pages 96-108, March.
    8. Alidaee, Bahram & Ahmadian, Ahmad, 1993. "Two parallel machine sequencing problems involving controllable job processing times," European Journal of Operational Research, Elsevier, vol. 70(3), pages 335-341, November.
    9. Plateau, M.-C. & Rios-Solis, Y.A., 2010. "Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations," European Journal of Operational Research, Elsevier, vol. 201(3), pages 729-736, March.
    10. Edis, Emrah B. & Oguz, Ceyda & Ozkarahan, Irem, 2013. "Parallel machine scheduling with additional resources: Notation, classification, models and solution methods," European Journal of Operational Research, Elsevier, vol. 230(3), pages 449-463.
    11. Kabir Rustogi & Vitaly A. Strusevich, 2013. "Parallel Machine Scheduling: Impact of Adding Extra Machines," Operations Research, INFORMS, vol. 61(5), pages 1243-1257, October.
    12. Geurtsen, M. & Didden, Jeroen B.H.C. & Adan, J. & Atan, Z. & Adan, I., 2023. "Production, maintenance and resource scheduling: A review," European Journal of Operational Research, Elsevier, vol. 305(2), pages 501-529.
    13. Briskorn, Dirk & Davari, Morteza & Matuschke, Jannik, 2021. "Single-machine scheduling with an external resource," European Journal of Operational Research, Elsevier, vol. 293(2), pages 457-468.
    14. Burdett, Robert L. & Kozan, Erhan, 2018. "An integrated approach for scheduling health care activities in a hospital," European Journal of Operational Research, Elsevier, vol. 264(2), pages 756-773.
    15. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    16. Tjark Vredeveld & Cor Hurkens, 2002. "Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 175-189, May.
    17. Patterson, S.R. & Kozan, E. & Hyland, P., 2017. "Energy efficient scheduling of open-pit coal mine trucks," European Journal of Operational Research, Elsevier, vol. 262(2), pages 759-770.
    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. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    2. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    3. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    4. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    5. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    6. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    7. Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    8. Teobaldo Bulhões & Ruslan Sadykov & Anand Subramanian & Eduardo Uchoa, 2020. "On the exact solution of a large class of parallel machine scheduling problems," Journal of Scheduling, Springer, vol. 23(4), pages 411-429, August.
    9. Plateau, M.-C. & Rios-Solis, Y.A., 2010. "Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations," European Journal of Operational Research, Elsevier, vol. 201(3), pages 729-736, March.
    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. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    12. 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.
    13. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).
    14. Zhi‐Long Chen & Warren B. Powell, 2003. "Exact algorithms for scheduling multiple families of jobs on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 823-840, October.
    15. Yang-Kuei Lin & Yin-Yi Chou, 2020. "A hybrid genetic algorithm for operating room scheduling," Health Care Management Science, Springer, vol. 23(2), pages 249-263, June.
    16. Xiaoyun Xiong & Peng Zhou & Yunqiang Yin & T. C. E. Cheng & Dengfeng Li, 2019. "An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 502-516, September.
    17. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    18. Yung-Chia Chang & Kuei-Hu Chang & Ching-Ping Zheng, 2022. "Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem Regarding Printed Circuit Boards," Mathematics, MDPI, vol. 10(13), pages 1-21, July.
    19. Daniel D. Zeng & J. Leon Zhao, 2005. "Effective Role Resolution in Workflow Management," INFORMS Journal on Computing, INFORMS, vol. 17(3), pages 374-387, August.
    20. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.

    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:eee:ejores:v:316:y:2024:i:3:p:856-872. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.