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

Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis

Author

Listed:
  • Yu, Renjie
  • Oron, Daniel

Abstract

We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fixed recharging period. Our focus is on two due date-related scheduling criteria: minimizing the number of late jobs and maximizing the weighted number of jobs completed exactly at their due dates. This study aims to analyze the parameterized tractability of the two problems and develop fixed-parameter algorithms with respect to three natural parameters: the number of different due dates vd, the number of different processing times vp, and the number of different energy consumptions ve. Following the proofs of NP-hardness across several contexts, we demonstrate that both problems remain intractable when parameterized by vd and vp. To complement our results, we show that both problems become fixed-parameter tractable (FPT) when parameterized by ve and vd, and are solvable in polynomial time when both ve and vp are constant.

Suggested Citation

  • Yu, Renjie & Oron, Daniel, 2025. "Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis," European Journal of Operational Research, Elsevier, vol. 324(1), pages 40-48.
    • Handle: RePEc:eee:ejores:v:324:y:2025:i:1:p:40-48
    DOI: 10.1016/j.ejor.2025.01.007
    as

    Download full text from publisher

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

    for a different version of it.

    References listed on IDEAS

    as
    1. Danny Hermelin & Matthias Mnich & Simon Omlor, 2024. "Serial batching to minimize the weighted number of tardy jobs," Journal of Scheduling, Springer, vol. 27(6), pages 545-556, December.
    2. Yunqiang Yin & T. C. E. Cheng & Du-Juan Wang & Chin-Chia Wu, 2017. "Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs," Journal of Scheduling, Springer, vol. 20(4), pages 313-335, August.
    3. Sally Martin & Jeffrey Martin & Polin Lai, 2019. "International container design regulations and ISO standards: are they fit for purpose?," Maritime Policy & Management, Taylor & Francis Journals, vol. 46(2), pages 217-236, February.
    4. Danny Hermelin & Shlomo Karhi & Michael Pinedo & Dvir Shabtay, 2021. "New algorithms for minimizing the weighted number of tardy jobs on a single machine," Annals of Operations Research, Springer, vol. 298(1), pages 271-287, March.
    5. Claire Hanen & Alix Munier Kordon, 2024. "Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines," Journal of Scheduling, Springer, vol. 27(2), pages 119-133, April.
    6. Danny Hermelin & Dvir Shabtay & Nimrod Talmon, 2019. "On the parameterized tractability of the just-in-time flow-shop scheduling problem," Journal of Scheduling, Springer, vol. 22(6), pages 663-676, December.
    7. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    8. Gur Mosheiov & Daniel Oron & Dvir Shabtay, 2022. "On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates," Journal of Scheduling, Springer, vol. 25(5), pages 577-587, October.
    9. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    10. Renhua Li & Leonie U Hempel & Tingbo Jiang, 2015. "A Non-Parametric Peak Calling Algorithm for DamID-Seq," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-12, March.
    11. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.
    12. Cui, Shaohua & Gao, Kun & Yu, Bin & Ma, Zhenliang & Najafi, Arsalan, 2023. "Joint optimal vehicle and recharging scheduling for mixed bus fleets under limited chargers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    13. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    14. Shabtay, Dvir & Gerstl, Enrique, 2024. "Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 316(3), pages 887-898.
    15. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    16. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    17. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    18. Pottel, Steffen & Goel, Asvin, 2022. "Scheduling activities with time-dependent durations and resource consumptions," European Journal of Operational Research, Elsevier, vol. 301(2), pages 445-457.
    19. Tan, Zhen & Fu, Guanqi, 2024. "Just-in-time scheduling problem with affine idleness cost," European Journal of Operational Research, Elsevier, vol. 313(3), pages 954-976.
    20. Boccia, Maurizio & Masone, Adriano & Sterle, Claudio & Murino, Teresa, 2023. "The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach," European Journal of Operational Research, Elsevier, vol. 307(2), pages 590-603.
    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. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    2. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    3. Dvir Shabtay, 2023. "A new perspective on single-machine scheduling problems with late work related criteria," Annals of Operations Research, Springer, vol. 322(2), pages 947-966, March.
    4. Zhou, Yu & Meng, Qiang & Ong, Ghim Ping, 2022. "Electric Bus Charging Scheduling for a Single Public Transport Route Considering Nonlinear Charging Profile and Battery Degradation Effect," Transportation Research Part B: Methodological, Elsevier, vol. 159(C), pages 49-75.
    5. Tingxin Wen & Haoting Meng, 2025. "Time-Dependent Multi-Center Semi-Open Heterogeneous Fleet Path Optimization and Charging Strategy," Mathematics, MDPI, vol. 13(7), pages 1-27, March.
    6. Ana Bricia Galindo-Muro & Riccardo Cespi & Stephany Isabel Vallarta-Serrano, 2023. "Applications of Electric Vehicles in Instant Deliveries," Energies, MDPI, vol. 16(4), pages 1-18, February.
    7. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    8. Su, Yue & Dupin, Nicolas & Parragh, Sophie N. & Puchinger, Jakob, 2024. "A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    9. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    10. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    11. Alberto Ceselli & Ángel Felipe & M. Teresa Ortuño & Giovanni Righini & Gregorio Tirado, 2021. "A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies," SN Operations Research Forum, Springer, vol. 2(1), pages 1-33, March.
    12. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    13. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    14. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    15. Azra Ghobadi & Mohammad Fallah & Reza Tavakkoli-Moghaddam & Hamed Kazemipoor, 2022. "A Fuzzy Two-Echelon Model to Optimize Energy Consumption in an Urban Logistics Network with Electric Vehicles," Sustainability, MDPI, vol. 14(21), pages 1-31, October.
    16. Najafi, Arsalan & Gao, Kun & Wang, Hua & Jasinski, Michal & Parishwad, Omkar & Cui, Shaohua & Liu, Xiaohan, 2025. "Joint charging scheduling of electric buses and active power flexibility integration," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 197(C).
    17. Koyuncu, Işıl & Yavuz, Mesut, 2019. "Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 605-623.
    18. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    19. Garside, Annisa Kesy & Ahmad, Robiah & Muhtazaruddin, Mohd Nabil Bin, 2024. "A recent review of solution approaches for green vehicle routing problem and its variants," Operations Research Perspectives, Elsevier, vol. 12(C).
    20. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:324:y:2025:i:1:p:40-48. 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.