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

Renjie Yu and Daniel Oron

European Journal of Operational Research, 2025, vol. 324, issue 1, 40-48

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.

Keywords: Single machine; Parameterized complexity; FPT; XP; W[t] (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725000323
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:324:y:2025:i:1:p:40-48

DOI: 10.1016/j.ejor.2025.01.007

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().