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

Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches

Author

Listed:
  • Tian, Zheng
  • Zheng, Li

Abstract

Electricity costs account for a relatively large proportion of total production costs in many energy-intensive manufacturing industries. And energy-efficient scheduling is getting increasing attention from researchers owing to its wide real-world applications and computational challenges. In this study, the single-machine parallel-batch scheduling problem with non-identical job sizes under time-of-use electricity prices is investigated. The objective is to minimise the total energy consumption cost such that the makespan does not exceed a given deadline. First, an improved time-slot-indexed formulation is proposed to eliminate symmetric solutions. Subsequently, a new set partition-based formulation is developed. To the best of our knowledge, there is no exact algorithm for this problem, except for some formulations solved by off-the-shelf solvers. To address this problem, a branch-and-price algorithm is developed with a novel and efficient branching rule. In addition, a column-generation-based heuristic is proposed to solve larger-scale instances. Extensive numerical experiments show that the efficiency of the branch-and-price algorithm is significantly better than that of off-the-shelf solvers, and many instances with up to 100 jobs could be solved to optimality within a 20-minute computational time limit for the first time. The column-generation-based heuristic can efficiently provide better solutions than existing heuristics (2.75% average gap in three minutes on instances with 100 jobs and 3.12% average gap in ten minutes on instances with 200 jobs).

Suggested Citation

  • Tian, Zheng & Zheng, Li, 2024. "Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches," European Journal of Operational Research, Elsevier, vol. 312(2), pages 512-524.
    • Handle: RePEc:eee:ejores:v:312:y:2024:i:2:p:512-524
    DOI: 10.1016/j.ejor.2023.07.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723005507
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.07.012?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. Gahm, Christian & Denz, Florian & Dirr, Martin & Tuma, Axel, 2016. "Energy-efficient scheduling in manufacturing companies: A review and research framework," European Journal of Operational Research, Elsevier, vol. 248(3), pages 744-757.
    2. Sung, C. S. & Choung, Y. I., 2000. "Minimizing makespan on a single burn-in oven in semiconductor manufacturing," European Journal of Operational Research, Elsevier, vol. 120(3), pages 559-574, February.
    3. Catanzaro, Daniele & Pesenti, Raffaele & Ronco, Roberto, 2023. "Job scheduling under Time-of-Use energy tariffs for sustainable manufacturing: a survey," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1091-1109.
    4. Eglese, R. W., 1990. "Simulated annealing: A tool for operational research," European Journal of Operational Research, Elsevier, vol. 46(3), pages 271-281, June.
    5. Masmoudi, Oussama & Delorme, Xavier & Gianessi, Paolo, 2019. "Job-shop scheduling problem with energy consideration," International Journal of Production Economics, Elsevier, vol. 216(C), pages 12-22.
    6. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    7. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    8. Peng Wu & Junheng Cheng & Feng Chu, 2021. "Large-scale energy-conscious bi-objective single-machine batch scheduling under time-of-use electricity tariffs via effective iterative heuristics," Annals of Operations Research, Springer, vol. 296(1), pages 471-494, January.
    9. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    10. Melouk, Sharif & Damodaran, Purushothaman & Chang, Ping-Yu, 2004. "Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing," International Journal of Production Economics, Elsevier, vol. 87(2), pages 141-147, January.
    11. Ozturk, Onur, 2020. "A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 432-443.
    12. Luo, Hao & Du, Bing & Huang, George Q. & Chen, Huaping & Li, Xiaolin, 2013. "Hybrid flow shop scheduling considering machine electricity consumption cost," International Journal of Production Economics, Elsevier, vol. 146(2), pages 423-439.
    13. Kan Fang & Nelson A. Uhan & Fu Zhao & John W. Sutherland, 2016. "Scheduling on a single machine under time-of-use electricity tariffs," Annals of Operations Research, Springer, vol. 238(1), pages 199-227, March.
    14. Kan Fang & Nelson Uhan & Fu Zhao & John Sutherland, 2016. "Scheduling on a single machine under time-of-use electricity tariffs," Annals of Operations Research, Springer, vol. 238(1), pages 199-227, March.
    15. Renan Spencer Trindade & Olinto César Bassi de Araújo & Marcia Helena Costa Fampa & Felipe Martins Müller, 2018. "Modelling and symmetry breaking in scheduling problems on batch processing machines," International Journal of Production Research, Taylor & Francis Journals, vol. 56(22), pages 7031-7048, November.
    16. Yang, Fan & Davari, Morteza & Wei, Wenchao & Hermans, Ben & Leus, Roel, 2022. "Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families," European Journal of Operational Research, Elsevier, vol. 303(2), pages 602-615.
    17. A. Alfieri & A. Druetto & A. Grosso & F. Salassa, 2021. "Column generation for minimizing total completion time in a parallel-batching environment," Journal of Scheduling, Springer, vol. 24(6), pages 569-588, December.
    18. Onur Ozturk, 2020. "A bi-criteria optimization model for medical device sterilization," Annals of Operations Research, Springer, vol. 293(2), pages 809-831, October.
    19. Husseinzadeh Kashan, Ali & Ozturk, Onur, 2022. "Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes," Omega, Elsevier, vol. 112(C).
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Yu Ni & Shufen Dai & Shuaipeng Yuan & Bailin Wang & Zhuolun Zhang, 2024. "Model and Algorithm for a Two-Machine Group Scheduling Problem with Setup and Transportation Time," Mathematics, MDPI, vol. 12(6), pages 1-12, March.

    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. Zhang, Han & Li, Kai & Jia, Zhao-hong & Chu, Chengbin, 2023. "Minimizing total completion time on non-identical parallel batch machines with arbitrary release times using ant colony optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1024-1046.
    2. Catanzaro, Daniele & Pesenti, Raffaele & Ronco, Roberto, 2023. "Job scheduling under Time-of-Use energy tariffs for sustainable manufacturing: a survey," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1091-1109.
    3. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    4. Husseinzadeh Kashan, Ali & Ozturk, Onur, 2022. "Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes," Omega, Elsevier, vol. 112(C).
    5. Seokgi Lee & Mona Issabakhsh & Hyun Woo Jeon & Seong Wook Hwang & Byung Chung, 2020. "Idle time and capacity control for a single machine scheduling problem with dynamic electricity pricing," Operations Management Research, Springer, vol. 13(3), pages 197-217, December.
    6. Xiangxin An & Guojin Si & Tangbin Xia & Qinming Liu & Yaping Li & Rui Miao, 2022. "Operation and Maintenance Optimization for Manufacturing Systems with Energy Management," Energies, MDPI, vol. 15(19), pages 1-19, October.
    7. Shen, Liji & Dauzère-Pérès, Stéphane & Maecker, Söhnke, 2023. "Energy cost efficient scheduling in flexible job-shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 310(3), pages 992-1016.
    8. Gaggero, Mauro & Paolucci, Massimo & Ronco, Roberto, 2023. "Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs," European Journal of Operational Research, Elsevier, vol. 311(3), pages 845-866.
    9. Heydar, Mojtaba & Mardaneh, Elham & Loxton, Ryan, 2022. "Approximate dynamic programming for an energy-efficient parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 302(1), pages 363-380.
    10. Catanzaro, Daniele & Pesenti, Raffaele & Ronco, Roberto, 2021. "Job Scheduling under Time-of-Use Energy Tariffs for Sustainable Manufacturing: A Survey," LIDAM Discussion Papers CORE 2021019, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Ghorbanzadeh, Masoumeh & Ranjbar, Mohammad, 2023. "Energy-aware production scheduling in the flow shop environment under sequence-dependent setup times, group scheduling and renewable energy constraints," European Journal of Operational Research, Elsevier, vol. 307(2), pages 519-537.
    12. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    13. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    14. Michal Penn & Tal Raviv, 2021. "Complexity and algorithms for min cost and max profit scheduling under time-of-use electricity tariffs," Journal of Scheduling, Springer, vol. 24(1), pages 83-102, February.
    15. Peng Wu & Junheng Cheng & Feng Chu, 2021. "Large-scale energy-conscious bi-objective single-machine batch scheduling under time-of-use electricity tariffs via effective iterative heuristics," Annals of Operations Research, Springer, vol. 296(1), pages 471-494, January.
    16. Hongliang Zhang & Yujuan Wu & Ruilin Pan & Gongjie Xu, 2021. "Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs," Journal of Intelligent Manufacturing, Springer, vol. 32(1), pages 91-112, January.
    17. Park, Myoung-Ju & Ham, Andy, 2022. "Energy-aware flexible job shop scheduling under time-of-use pricing," International Journal of Production Economics, Elsevier, vol. 248(C).
    18. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    19. Nascimento, Paulo Jorge & Silva, Cristóvão & Antunes, Carlos Henggeler & Moniz, Samuel, 2024. "Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 92-110.
    20. Chen, Bo & Zhang, Xiandong, 2019. "Scheduling with time-of-use costs," European Journal of Operational Research, Elsevier, vol. 274(3), pages 900-908.

    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:312:y:2024:i:2:p:512-524. 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.