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
研究了单机调度中作业需消耗可补充能量且补充时间固定的问题，分析了最小化延迟作业数和最大化准时加权作业数两个目标的参数化复杂度，发现当参数为不同能耗数和不同截止期数时问题可固定参数求解。
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 v d , the number of different processing times v p , and the number of different energy consumptions v e . Following the proofs of NP -hardness across several contexts, we demonstrate that both problems remain intractable when parameterized by v d and v p . To complement our results, we show that both problems become fixed-parameter tractable (FPT) when parameterized by v e and v d , and are solvable in polynomial time when both v e and v p are constant. • Single machine scheduling problems with renewable energy constraints are considered. • Minimizing the number of late jobs is shown to be strongly NP-hard. • Minimizing the weighted number of Just in Time jobs is shown to be strongly NP-hard. • The complexity of both problems is investigated under fixed parameter settings. • Efficient algorithms are developed for parameter combinations with upper bounds.