PaperlayerView exact revision on arXiv

Source-linked AI summary

Job Scheduling with Battery Recharging Constraints

Rudransh Kumar, Nima Nasiri, Jared Paul, Sathish Gopalakrishnan

arXiv:2610.02447v1cs.DS

TL;DR

Recharge duration depends on acquired energy, so scheduling must account for both job order and charging decisions rather than assuming fixed recharge durations. The paper analyzes partial and complete recharging, with and without setup time, classifies the resulting variants, and gives approximation algorithms for selected hard cases.

  • Problem

    Existing models either fix recharge duration or treat the battery as a routing budget, while this problem makes recharge duration depend on acquired energy and lets the scheduler choose job order and recharges.

    Source: §1 · p. 2

  • Method

    The paper studies non-preemptive job scheduling under partial or complete recharging, with optional deadlines and setup time, across four objectives and four relationships between execution time and energy demand.

    Source: §1.1 · p. 2, §1 · p. 2

  • Results

    Without setup time, 14 of 16 partial-recharging variants are polynomial and the two unrelated-parameter cases are NP-hard; complete recharging has four polynomial equal-energy cases and 12 NP-hard cases, while setup time leaves eight equal-energy cases polynomial and makes the other 24 strongly NP-hard when it is input.

    Source: §1.2 · p. 3, §1.3 · p. 3

  • Takeaways & Limitations

    The paper classifies solvable and hard cases across recharging policies and job structures, and provides approximation algorithms for selected hard variants.

    Source: §12 · p. 53

    The analysis assumes offline jobs with constant-rate charging and does not validate schedules on physical batteries or chargers; the setup-time average-completion guarantee requires an empty battery and positive demands.

    Source: §1.4 · p. 4, §12 · p. 53

Abstract

from arXiv · show

A battery-powered device, such as a delivery drone that works from a depot, must stop to recharge between jobs, and the time spent recharging delays every job that follows. Scheduling models that fix the duration of a recharge do not describe a device whose recharge takes longer when it acquires more energy. We study a single device that executes a batch of non-preemptive jobs with known execution times, energy demands, and optional deadlines. Under \emph{partial recharging} the device may acquire any amount of energy between jobs; under \emph{complete recharging} every recharge fills the battery. Four objectives and four relationships between execution time and energy demand give 32 variants. When acquiring $q$ units of energy takes $q$ time units, we show that 14 of the 16 partial-recharging variants are polynomial, and we give a tight 2-approximation for the average completion time, one of the two NP-hard variants. Under complete recharging, the four variants with equal energy demands are polynomial and the other 12 are NP-hard; for makespan we give a $5/4$-approximation. When each recharge also incurs a fixed \emph{setup time} $h$, the equal-energy variants remain polynomial and the other 24 are strongly NP-hard if $h$ is part of the input. For these we give exact algorithms that are exponential only in the number of jobs, and approximation algorithms for makespan and, when the battery starts empty, for the weighted average completion time. Experiments on synthetic and trace-derived job sets compare the algorithms with exact optima. The model is offline and deterministic, and we have not validated the schedules on hardware.

1 Introduction

The paper formalizes scheduling jobs whose energy-linked recharges delay later work, with partial or complete recharging and optional setup time. It classifies tractable and hard variants and gives approximation algorithms for selected hard cases, within an offline model that assumes fixed job demands and constant-rate charging.

1.1 The Scheduling-and-Charging Problem

  • The Scheduling-and-Charging Problem schedules non-preemptive jobs with known execution times, energy demands, and optional deadlines, choosing job order and recharges under partial or complete recharging.The paper considers average completion time, makespan, maximum tardiness, and number of tardy jobs, across four relationships between execution time and energy demand.Source: §1.1 · pp. 2–3, §1 · p. 2

1.2 Results without Setup Time

  • Without setup time, 14 of 16 partial-recharging variants are polynomial; the two hard cases have unrelated job parameters, with a tight 2-approximation for average completion time and a pseudo-polynomial algorithm for tardy-job minimization.For average completion time, a variant improves the factor to 2 − 2/(n + 1).Source: §1.2 · p. 3
  • With complete recharging, the four equal-energy variants are polynomial and the other 12 are NP-hard; a makespan algorithm achieves a 5/4 approximation.The makespan result uses the fact that total recharging time depends on which jobs execute after the last recharge.Source: §1.2 · p. 3

1.3 Results with Setup Time

  • With setup time, the eight equal-energy variants remain polynomial, while the other 24 are strongly NP-hard when setup time is part of the input.For unequal demands, the paper gives exact algorithms exponential in the number of jobs and approximation algorithms for makespan and, under stated conditions, weighted average completion time.Source: §1.3 · pp. 3–4

1.4 Scope

  • The model applies after routing fixes each job’s duration and energy demand; it assumes constant-rate charging and does not validate schedules on physical hardware.It excludes charging windows and competition among multiple devices for chargers.Source: §1.4 · p. 4

1.5 Relation to the Conference Version

  • Compared with the 2022 conference version, this paper resolves the open partial-recharging average-completion case, adds makespan results and computational evaluation, and introduces setup-time results.The conference version left open average completion time under partial recharging with unrelated parameters.Source: §1.5 · p. 4

2 System Model

The system model schedules non-preemptive jobs on one battery-powered device, with charging choices and setup time affecting when jobs can run. It formalizes schedules and four objectives, then classifies the resulting variants by complexity.

2.1 Jobs and Battery

  • Jobs are available at time zero, run non-preemptively, and have execution times, energy demands, and sometimes deadlines; charging is linear but omits slower near-full charging.Every job must fit within battery capacity, and one energy unit takes one time unit to acquire.Source: §2.1 · pp. 4–5
  • The four job classes distinguish equal energy demands, equal execution times, energy equal to execution time, and unrestricted relationships.These are instance classes, and one instance may satisfy multiple restrictions.Source: §2.1 · p. 5

2.2 Recharging and Setup Time

  • A positive recharge incurs setup time h plus the time to acquire energy; a zero recharge has no cost, and no recharge follows the last job.With h = 0, acquiring q units takes q time units; under complete recharging, a positive recharge fills the battery to its target.Source: §2.2 · p. 5

2.3 Schedules

  • Each schedule specifies a job permutation and recharge amounts, with battery-feasibility constraints; a group is a maximal sequence without positive recharging.Idle time is omitted because removing it preserves feasibility and cannot worsen the objectives.Source: §2.3 · pp. 5–6

2.4 Objectives

  • The model minimizes sum of completion times, makespan, maximum tardiness, or the number of jobs completed after their deadlines.Sum of completion times also minimizes average completion time and, because total execution time is fixed, average waiting time.Source: §2.4 · p. 6, Number of tardy jobs, 𝑈= Í𝑛 · p. 6

Number of tardy jobs, 𝑈= Í𝑛

  • Without setup time, makespan minimization is equivalent to minimizing acquired energy; with setup time, the number of charging sessions also matters.Consequently, acquiring the least energy need not yield the least makespan when setup time is present.Source: Number of tardy jobs, 𝑈= Í𝑛 · p. 6

2.5 Classification

  • Without setup time, partial recharging is hard only for arbitrary-parameter sum of completion times and tardy-job count; complete recharging is hard except for equal-energy jobs.With setup time, equal-energy variants are polynomial and the other three classes are strongly NP-hard under both policies.Source: §2.5 · p. 6, Table 1 · p. 7

3 Complete Recharging without Setup Time

This section classifies the 16 complete-recharging variants without setup time, giving polynomial algorithms for equal energy demands and hardness results for unequal demands. It also presents objective-specific results, including a 5/4-approximation for makespan and reductions to subset-sum problems.

3.1 Minimizing Sum of Completion Times (SCT)

  • Equal-energy SCT is solvable in O(n log n), while unequal-demand SCT is NP-hard for equal execution times, e_i = b_i, and arbitrary relationships.The equal-energy algorithm sorts jobs by SJF and evaluates possible first-group sizes; the hardness construction encodes an equal-cardinality partition.Source: §3.1 · p. 8
  • Unequal-demand SCT is NP-hard even when all jobs have equal execution time, and also when e_i = b_i or the relationship is arbitrary.The construction uses group selection to encode an equal-cardinality partition.Source: §3.1 · p. 8

3.2 Minimizing Maximum Tardiness (𝑇max)

  • For equal energy, EDF order with dynamic programming minimizes maximum tardiness in O(n^2); unequal-demand variants are NP-hard for all three execution-time relationships.The dynamic program chooses recharge boundaries between groups after fixing the EDF order.Source: §3.2 · p. 9, §3.2.2 · p. 9

3.2.2 Other Cases

  • Unequal-demand maximum tardiness is NP-hard for equal execution times, e_i = b_i, or arbitrary relationships, by assigning every job deadline zero.With zero deadlines, maximum tardiness equals makespan.Source: §3.2.2 · p. 9

3.3 Minimizing Number of Tardy Jobs (𝑈)

  • Equal-energy minimum tardy-job count is solved by dynamic programming in O(n^3), retaining the earliest completion for each timely-job count and battery level.For equal execution times, e_i = b_i, or arbitrary relationships, minimizing the number of tardy jobs is NP-hard.Source: §3.3 · p. 9, §3.3.2 · p. 10

3.4 Minimizing Makespan (𝐶max)

  • For equal energy, makespan is solvable in O(n); total recharge time depends on the head jobs, and any maximum-capacity final group minimizes makespan.The final group contains at most min(n, floor(Bmax/b)) jobs; with unequal demands, choosing a high-energy feasible final group becomes subset selection.Source: §3.4 · pp. 10, 12

3.4.2 Other Cases: NP-hardness

  • Unequal-demand makespan is NP-hard for equal execution times, e_i = b_i, and arbitrary relationships, via a reduction from Subset-Sum.The reduction makes the feasible final-group energy correspond to a subset sum.Source: §3.4.2 · p. 12

3.4.3 Other Cases: Reductions to Subset-Sum Minimization and Maximization

  • Makespan strictly reduces to Subset-Sum Minimization in O(n), so an SS-MIN approximation transfers with no larger relative error.For scale-invariant SS-MIN algorithms with an appropriate witnessing family, the reduction also transfers the same worst-case ratio to valid scheduling instances with equal execution times and one extra zero-energy job.Source: §3.4.3 · pp. 12–13
  • When total energy exceeds 2B_max, minimizing makespan under complete recharging strictly reduces to SS-MAX in O(n) time.The reduction uses target C = B_max.Source: §3.4.3 · p. 14
  • Replacing the subset-sum subroutines with (1 + ε)-approximation algorithms gives a (1 + ε) guarantee for complete-recharging makespan.The resulting absolute error depends on ε and battery capacity, not on the number of jobs.Source: §3.4.3 · p. 14
  • A 5/4-approximation for makespan follows when the head-selection routine is a 5/4-approximation for SS-MIN and the final-group routine achieves at least 3/4 of the SS-MAX optimum.The implementation uses size-class subroutines and runs in O(n log n).Source: §3.4.3 · pp. 14–15
  • Equal-energy demands yield polynomial algorithms for all four objectives, while the other three job classes are NP-hard for each objective.For the NP-hard classes, makespan has a 5/4 approximation; approximation of the other objectives remains open.Source: §3.4.3 · p. 15

4 Partial Recharging without Setup Time

This section studies partial recharging without setup time and characterizes the complexity of its scheduling objectives across different energy–execution relationships. Overall, 14 of 16 variants are polynomial, while the two NP-hard variants have pseudo-polynomial exact algorithms and factor-two algorithms.

4 Partial Recharging without Setup Time

  • For any fixed job order, recharging only each job’s energy deficit minimizes every completion time, so optimization reduces to choosing the job order.This minimum-recharge construction applies to any non-decreasing objective.Source: §4 · pp. 15–16

4.1.1 Structured Execution Times and Energy Costs

  • Sum-of-completion-times scheduling takes O(n log n) time when energy demands are equal, execution times are equal, or execution time equals energy demand.These cases satisfy the condition that ordering by execution time also orders jobs by execution time plus energy demand.Source: §4.1.1 · p. 16
  • Arbitrary execution times and energy demands make sum-of-completion-times scheduling binary NP-hard when the initial battery charge is positive.When the initial charge is zero, sorting by execution time plus energy demand instead gives an O(n log n) optimum.Source: §4.1.1 · p. 17
  • A 2-approximation for arbitrary sum-of-completion-times instances runs in O(n log n), and its factor 2 is tight.The algorithm selects a prefix by execution time plus energy demand, reorders that prefix by execution time, and uses the former order for the suffix; the tight example’s ratio 2λ/(λ + 2) approaches 2 as λ grows.Source: §4.1.1 · pp. 20–21
  • Whether a polynomial algorithm achieves a constant factor below 2 independent of the number of jobs remains open.The final-job enumeration can improve the bound for each fixed job count, but is not exact in general.Source: §4.1.1 · p. 22

4.2 Minimizing Maximum Tardiness (Tmax)

  • Maximum tardiness is minimized by earliest-deadline-first ordering in O(n log n) time for all four energy-execution relationships.Adjacent exchanges of jobs out of deadline order preserve the completion time of the second job and all later jobs, and do not increase the pair’s maximum tardiness.Source: §4.2 · p. 22

4.2 Minimizing Maximum Tardiness (𝑇max)

  • An earliest-deadline-first (EDF) schedule minimizes maximum tardiness in O(n log n) time.Swapping adjacent deadline inversions preserves later completion times and does not increase the pair’s maximum tardiness.Source: §4.2 · p. 22

4.3 Minimizing Number of Tardy Jobs (𝑈)

  • Minimizing tardy jobs takes O(n log n) time when all battery capacities are equal, all energy demands are equal, or each energy demand equals its battery capacity.The EDF-based Moore–Hodgson rule discards the selected job with largest weight whenever a deadline is missed.Source: §4.3 · pp. 23–24
  • With arbitrary energy demands and battery capacities, minimizing tardy jobs is NP-hard, but a pseudo-polynomial dynamic program solves it.The dynamic program tracks finish time and remaining battery, which determine whether later jobs can meet deadlines.Source: §4.3 · pp. 24–25

4.4 Minimizing Makespan (𝐶max)

  • Under partial recharging, every schedule that recharges only as needed has the same makespan, regardless of job order; the optimum is computable in O(n) time for all four energy–execution relationships.Minimum total recharging is max(0, total battery demand − initial charge), so makespan is total execution time plus that amount.Source: §4.4 · p. 25
  • Partial recharging without setup time is polynomial in 14 of 16 variants; the two NP-hard variants have arbitrary energy and battery parameters, with a factor-two guarantee for sum of completion times and a pseudo-polynomial exact algorithm for tardy-job count.The analysis relies on the partial-recharging property that total prefix recharge depends only on the jobs in the prefix, a property that fails with fixed recharge setup costs.Source: §4.4 · p. 25

5 Evaluation without Setup Time

The evaluation compares the approximation algorithms with exact optima, measures their runtime, and tests how workload and charging parameters affect results. It also compares the algorithms with simple heuristics on synthetic and trace-derived batches.

5 Evaluation without Setup Time

  • The evaluation used 30 synthetic job sets and six sets derived from public sensor-current traces, varying capacity and charging rate.The trace-derived jobs were fixed inputs to an offline model; job boundaries and battery and charger parameters were chosen by the authors.Source: §5 · pp. 25–26, §5.4 · pp. 31–32

5.1 Empirical Approximation Quality

  • The reported ratios describe tested job sets and parameter grids, and the schedules were not validated on physical batteries or chargers.The trace construction does not reproduce periodic traffic or test deadlines and protocol dependencies.Source: §5 · p. 26, §5.4 · p. 33

5.1.1 SCT under Partial Recharging

  • On 1,860 partial-recharging instances, A1’s mean ratios were 1.0186 for alternating jobs and 1.0084 for uniform jobs; its largest ratio was 1.1814.The two-job construction’s ratio 2λ/(λ + 2) approaches 2, while repeating that structure reduced observed ratios toward 1 over tested sizes.Source: §5.1.1 · p. 26, Figure 2 · p. 27, Figure 3 · p. 27

5.1.2 Makespan under Complete Recharging

  • On 1,300 complete-recharging instances, A2’s mean makespan ratio was 1.0119 and its largest was 1.0635.The total execution time contributes equally to A2’s and the optimal makespan, reducing the ratio relative to the subset-sum subroutine’s ratio.Source: §5.1.2 · p. 26, Figure 2 · p. 27, Table 3 · p. 28

5.2 Running-Time Scalability

  • At 100,000 jobs, median desktop runtimes were 75.5 ms for A1, 59.8 ms for A2, and 69.5 ms for SJF.These measurements include schedule construction and describe one desktop, not embedded hardware.Source: §5.2 · p. 27, Figure 4 · p. 28, Table 4 · p. 29

5.3 Workloads and Capacity/Charge-Rate Sensitivity

  • On synthetic bursty jobs, complete recharging increased optimal makespan by up to 18.18%; the two policy optima coincided on sampled delivery and warehouse jobs.Faster charging reduced the mean policy gap over tested settings, while increasing capacity did not always reduce it.Source: Table 5 · p. 29, Figure 5 · p. 30, §5.3 · p. 31

5.4 Experiments with Measured Sensor-Current Traces

  • On selected BLE/UWB windows, A1 attained the exact SCT optimum, the maximum policy gap was 0.0215%, and the maximum A2 excess was 0.1779%.The windows satisfied a pairwise ordering condition under which SJF with increasing-energy tie-breaking is optimal, regardless of feasible capacity and initial charge.Source: §5.4 · pp. 32–33

5.5 Comparison with Simple Scheduling Heuristics

  • On bursty workloads, A1’s mean SCT ratio was 1.01662, versus 1.37473 for SJF and 1.14524 for SSF.A1 improved on SSF in 215 configurations and tied in 757; against SJF it won 542, tied 409, and lost 21. A2 did not consistently improve on greedy final-group selection.Source: §5.5 · pp. 33–34, Table 6 · p. 33, Table 7 · p. 33

6 Partial Recharging with Setup Time

With setup time, each charging session adds delay, so partial-recharging schedules must optimize recharge amounts and positions together. Equal energy demands nevertheless permit exact polynomial-time algorithms for all four objectives.

6.1 Recharging for a Fixed Order

  • The partial-recharging normal form makes each session serve a consecutive job group, reducing recharge-amount choices to group boundaries.For a fixed order, the free prefix runs without recharging; later positive recharges begin with an empty battery, and the schedule ends with an empty battery.Source: §6.1 · pp. 34–35

6.2 Equal Energy Demands

  • For equal energy demands, SJF is optimal for SCT and EDF for maximum tardiness under either recharging policy.Under partial recharging, EDF followed by the fixed-order dynamic program solves maximum tardiness in O(n^3).Source: §6.2 · p. 36

6.2.1 Sum of Completion Times

  • SJF followed by marginal-cost allocation minimizes partial-recharging SCT in O(n log n) time and O(n) additional space.Source: §6.2.1 · p. 36

6.2.2 Makespan

  • Equal-energy partial-recharging makespan is optimal in O(n) time, and any job order suffices.The greedy construction attains the minimum session count and acquires exactly n b − B0 energy when recharging is needed.Source: §6.2.2 · p. 37

6.2.3 Number of Tardy Jobs

  • An EDF subset dynamic program with prefix minima minimizes the number of tardy jobs under partial recharging in O(n^3) time.Source: §6.2.3 · p. 37

6 Partial Recharging with Setup Time

  • Equal energy demands admit exact polynomial algorithms for all four objectives under partial recharging with setup time; the exchange arguments do not extend to unequal demands.Source: §6.2.3 · p. 38

7 Complete Recharging with Setup Time

Complete recharging fixes each positive recharge at the battery deficit, but residual energy can carry over between sessions. Exact polynomial algorithms remain available for equal-energy jobs across all four objectives.

7.1 Recharging for a Fixed Order

  • For a fixed order, only O(n) battery levels are reachable, keeping each dynamic-programming state space polynomial in n.The fixed-order complete-recharging makespan construction also minimizes makespan in O(n) time.Source: §7.1 · pp. 38–39

7.2 Equal Energy Demands

  • With equal energy demands, SJF is optimal for SCT and EDF for maximum tardiness; EDF with the deadline dynamic program takes O(n^3) time.Source: §7.2 · p. 39

7.2.1 Sum of Completion Times

  • Equal-energy complete-recharging SCT is solved in O(n log n) time by evaluating initial-prefix choices after filling each nonfinal charged group to capacity.SJF supplies the optimal order.Source: §7.2.1 · pp. 39–40

7.2.2 Makespan

  • For equal-energy makespan, the earliest feasible final suffix and lazy full recharges give an optimal O(n)-time construction.The final suffix contains min(n, m) jobs.Source: §7.2.2 · p. 40

7.2.3 Number of Tardy Jobs

  • The equal-energy tardy-job algorithm keeps the earliest feasible time for each count/battery state and runs in O(n^3).Its largest selected count gives the optimal timely prefix.Source: §7.2.3 · p. 40
  • Exact polynomial algorithms solve all four equal-energy objectives under complete recharging, although residual energy prevents the partial-recharging normal form.Only O(n) battery values are relevant to each fixed-order or equal-energy subproblem.Source: §7.2.3 · p. 40

8 Hardness with Setup Time

With setup time as part of the input, the three unequal-demand job classes are strongly NP-hard under either recharging policy. The reductions make the number of charging sessions encode a packing decision.

8 Hardness with Setup Time

  • Setup time makes the session count matter even when acquired energy is fixed, turning minimum-session feasibility into a packing problem.Source: §8 · p. 40
  • For either recharging policy, all four objectives are strongly NP-hard in the equal-execution, energy-equal-to-execution, and arbitrary job classes when setup time is an input.Makespan and both deadline objectives remain strongly NP-hard even at h = 1.Source: §8 · p. 41
  • The sum-of-completion-times hardness proof chooses setup time from the input, so it does not establish hardness for every prescribed positive constant setup time.Source: §8 · p. 41
  • Unless P=NP, unequal-demand deadline classes have no polynomial-time approximation with a finite multiplicative factor on all instances.This result relies on instances with optimum zero and does not rule out additive guarantees or a promise excluding those instances.Source: §8 · p. 41

9 Algorithms for Unequal Demands with Setup Time

For unequal-demand jobs with setup time, the section develops objective-specific exact subset algorithms and approximations while examining the limits of zero-setup ordering rules. It shows that setup time must be incorporated into the sorting rule.

9.1 Subset Algorithms for Partial Recharging

  • Subset algorithms provide exact schedules for all variants, with general algorithms exponential in job count but independent of numerical battery capacity.For partial recharging, the subset/group recurrence enumerates at most 3^n subset/group pairs; the exact algorithms are intended for small instances and as reference optima.Source: §9 · p. 42, §9.1 · p. 43, §9.2 · p. 44

9.2 Subset Algorithms for Complete Recharging

  • Exact subset algorithms for complete recharging store reachable battery states and solve every variant, with running time exponential in the number of jobs.The algorithms serve small instances and as reference optima for the experiments.Source: §9.2 · p. 44

9.3 Recharging a Prescribed Job Order

  • For a prescribed job order, recharge amounts can be optimized exactly; makespan takes O(n) time, while other objectives have polynomial-time fixed-order algorithms.These algorithms accept arbitrary energy demands but do not make the supplied order globally optimal.Source: §9.3 · p. 45

9.4 Makespan Approximation

  • A factor-2 makespan approximation works under either recharging policy for arbitrary initial energy; with an empty battery, FFD gives a factor-3/2 approximation in O(n^2) time.The stronger guarantee requires B0 = 0; the factor-2 result covers arbitrary initial energy.Source: §9.4 · pp. 45–46

9.5 Sum of Completion Times Approximation

  • For an empty initial battery, positive job demands, and positive weights, a setup-dependent sorting and grouping construction gives weighted completion time at most 3 OPT under either policy.The construction sorts by (e_i + c b_i)/w_i; the guarantee does not cover zero-demand jobs or nonempty initial batteries.Source: §9.5 · pp. 46–47
  • With an empty battery and positive demands and weights, the weighted completion-time guarantee is 3 OPT, and the factor three is not known to be improvable.Observed largest ratios were 491/400 and 13/10; the zero-setup order by e_i + b_i cannot replace the setup-dependent key, even with optimal recharging.Source: §9.5 · pp. 46–47

9.6 Limits of the Zero-Setup Rules

  • Zero-setup rules can fail: EDF and Moore–Hodgson can miss feasible timely schedules, and the e_i + b_i order with optimal recharging has an unbounded SCT approximation ratio.For every m ≥ 2 and ε > 0, an instance makes that order’s SCT at least ((2m + 1)/3 − ε) times optimum under either policy.Source: §9.6 · p. 48
  • Ω(n^0.5) is the zero-setup order’s ratio even with optimal recharging; no matching upper bound is known, and setup time must enter the sorting rule.In the construction, the schedule ratio tends to (2m+1)/3 as h→∞.Source: §9.6 · p. 48
  • 4,021 is A2’s best complete-recharging makespan versus 3,021 for pairing each demand-two job with a demand-three job, exceeding 5/4.The example has six unit-execution jobs, demands (2, 2, 2, 3, 3, 3), Bmax = 5, B0 = 0, and h = 1,000; the pairing attains the lower bound.Source: §9.6 · p. 48
  • Use polynomial exact algorithms for equal energy demands, subset algorithms for small general instances, T24/T25 makespan approximations, and T26 for completion sums when the battery starts empty and every job needs energy.No approximation ratio is known for other job-order heuristics or for completion sums when initial energy is positive or any job has zero demand.Source: §9.6 · p. 48

10 Evaluation with Setup Time

The setup-time evaluation checks implementations against independent exact methods, then compares polynomial candidates with exact optima on paired synthetic instances. The observed performance is limited to small workloads and does not validate the algorithms on larger or physical-device workloads.

10.1 Correctness Checks

  • Independent enumeration and oracle checks agreed across thousands of tested instances, but finite comparisons indicate behavior on those inputs rather than proving correctness or approximation ratios.The checks included 3,418 small instances, seeded instances, and comparisons for fixed-order, equal-energy, subset, and approximation algorithms.Source: §10 · p. 49, §10.1 · p. 49
  • Across 7,532 policy/instance pairs, the factor-three SCT construction’s largest observed ratio was 491/400 without weights and 13/10 with weights.The checks also included 2,000 weighted comparisons; all observed ratios were below the proved factor of three.Source: §10.1 · p. 49

10.3 Limits of the Evaluation

  • The paired comparison used six-job synthetic sets, so it does not show how the polynomial algorithms perform on larger or more realistic workloads.The authors did not measure setup times or charging rates on a physical device.Source: §10.2 · p. 50, §10.3 · p. 51

10.2 Comparison on Paired Setup Times

  • The equal-energy algorithms were optimal in all 400 comparisons, while deadline-objective candidates missed at most two more jobs and had excess maximum tardiness up to 100 time units.For maximum tardiness, the largest excess was 99 under partial recharging and 100 under complete recharging; exact algorithms remain necessary to decide whether every deadline can be met.Source: §10.2 · pp. 50–51
  • The best candidate was optimal in 94–134 of 150 comparisons, while the largest observed makespan ratio was 159/109 under either policy.The largest observed SCT ratios were 198/149 under partial recharging and 1197/899 under complete recharging; these are sample observations, not guarantees.Source: §10.2 · p. 50

11 Related Work

Related work covers routing, device scheduling, recharge and setup models, batching, and energy-aware computing. The paper instead treats fixed job times and energy demands, studying the complexity of choosing job order and recharges.

11.1 UAV and Drone Scheduling

  • Drone routing work jointly plans tours and recharging, whereas this paper takes job times and energy demands as fixed inputs and studies ordering and recharging.Other drone models treat battery charge as a per-tour budget rather than an interleaved recharge process.Source: §11.1 · p. 51

11.2 Warehouse Robots and Electric Ground Vehicles

  • Warehouse-robot and electric-vehicle studies include batched routing, long-horizon charge scheduling, and fixed-route charging; the paper’s task sequence and operator-controlled recharging match the robot setting.Related vehicle work also jointly optimizes routing and charging.Source: §11.2 · p. 51

11.3 Recharge Durations and Setup Time

  • Fixed-duration recharge models differ from this paper’s amount-dependent recharge length, while processor setup models trigger setup through job-family switches rather than recharge decisions [2, 3].The models share a grouping consequence, but EDF order can fail once setup takes time.Source: §11.3 · p. 52

11.4 Batching and Packing

  • With an empty battery and partial recharging, makespan reduces to bin packing, yielding a 3/2 ratio via first-fit decreasing; complete recharging and arbitrary initial energy need separate arguments.The partial-recharging identity is makespan = E + S + hK*, where K* is the minimum number of bins.Source: §11.4 · p. 52

11.5 CubeSat and Nanosatellite Scheduling

  • Orbital charging windows distinguish nanosatellite scheduling from this model, whose hardness results assume recharging is available between any two jobs.Source: §11.5 · p. 52

11.6 Energy Harvesting and Intermittent Computing

  • Energy-harvesting models schedule around energy arrivals determined by the environment, whereas this model lets the operator choose when to recharge.Intermittent computing instead focuses on preserving computation across uncontrolled power interruptions.Source: §11.6 · pp. 52–53

11.7 Energy-Aware Scheduling

  • Other energy-aware scheduling work often treats stochastic energy or tunes execution to reduce energy, while this paper fixes each job’s energy demand and optimizes order and recharging.Related work also includes energy-harvesting and finite-horizon scheduling.Source: §11.7 · p. 53

12 Conclusions

The conclusions classify scheduling variants by recharge policy and setup cost, while the open problems mark limits in approximation guarantees and in the model’s physical validation.

12 Conclusions

  • Without setup time, partial recharging reduces to ordering: 14 of 16 variants are polynomial, while the two hard variants have unrelated job parameters.For complete recharging, equal-energy demands are the only polynomial case for each objective.Source: §12 · p. 53
  • With setup time as an input, equal-energy variants remain polynomial, but all objectives for the other three job classes are strongly NP-hard.Subset algorithms give exact schedules; makespan approximations have factors two for any initial energy and 3/2 for an empty battery, while the weighted-average factor-three rule requires an empty battery and positive demands.Source: §12 · p. 53
  • For partial-recharging average completion time, the 2-approximation is tight for its algorithm; complete-recharging makespan has a 5/4-approximation.A variant for partial-recharging average completion time has factor 2 − 2/(n + 1).Source: §12 · p. 53
  • The setup-time evaluation uses six-job instances, assumes offline scheduling and constant charging rates, and does not validate schedules on physical hardware.Without setup time, the classification is complete; with setup time, the guarantee for average completion time requires an empty battery and positive demands.Source: §12 · p. 53

Open Problems

  • A fully polynomial-time approximation scheme for partial-recharging average completion time remains possible; a constant factor below two independent of n is also unresolved.The hardness result uses binary-encoded inputs and is not strong NP-hardness.Source: Open Problems · p. 54
  • For setup-time average completion, factor three’s tightness and hardness at each fixed positive setup time remain open; the analysis excludes positive initial energy and zero-demand jobs.The zero-setup order by e_i + b_i has ratio Ω(√n), even with optimal recharging.Source: Open Problems · p. 54
  • For setup-time deadline objectives, no polynomial algorithm has a finite multiplicative guarantee on all instances unless P=NP.Additive guarantees and algorithms parameterized by job types or sessions are proposed directions.Source: Open Problems · p. 54
  • Convex recharge durations, energy-consuming setup, variable charger availability, and shared chargers remain model extensions; measured setup times and charging rates are needed to assess physical relevance.Lithium-ion charging slows above about 80% state of charge, suggesting a convex recharge duration that may alter the complexity classification.Source: Open Problems · p. 54

A Proofs

The appendix supplies proof materials omitted from the main text and establishes guarantees for two subset-sum routines used by A2.

A Proofs

  • The appendix gives group-exchange arguments omitted from the main text.Source: A Proofs · p. 57
  • It also supplies omitted dynamic programs and reduction details.Source: A Proofs · p. 57
  • The appendix proves the guarantees of the two subset-sum routines used by A2.Source: A Proofs · p. 57

A.1 Proof of Lemma L1 (SJF Within Groups)

The proof separates recharge and execution contributions to total completion time, then shows SJF minimizes the execution contribution without changing the recharge contribution.

A.1 Proof of Lemma L1 (SJF Within Groups)

  • Expanding completion formula (4) separates total completion time into recharge and execution contributions.Source: §A.1 · p. 58
  • With equal energy demands, reordering jobs within a group leaves the recharge contribution, term A, unchanged.Source: §A.1 · p. 58
  • SJF minimizes execution contribution, term B, by placing shorter jobs first, so any non-SJF schedule has a weakly larger sum of completion times.Source: §A.1 · p. 58

A.2 Proof of Lemma L2 (Full Interior Groups)

The proof transforms an optimal schedule by moving jobs from one interior group to the preceding group, preserving job order while controlling recharge contributions.

A.2 Proof of Lemma L2 (Full Interior Groups)

  • For an optimal schedule, an interior group smaller than m* must be followed by a group whose combined size exceeds m*, or merging them would improve the objective.Source: §A.2 · p. 58
  • Moving m* − m_a jobs from the succeeding group to the end of the preceding group preserves job order and execution contribution.Source: §A.2 · p. 58
  • The move replaces the groups’ recharge contribution and is no worse; iterating it yields the full-interior-group claim.Source: §A.2 · p. 58

A.3 Proof of Theorem T2 (SCT, Complete, NP-hard)

The proof reduces EquiPartition to complete-recharging scheduling by constructing jobs whose feasible two-group schedules encode a partition. Separate cost thresholds establish hardness for equal execution times and for jobs with execution time equal to energy demand.

Reduction conclusion

  • EquiPartition is NP-hard, and the reduction has polynomial encoding length; the two cost-threshold arguments establish hardness independently for both relationships.Unrestricted execution-time and energy-demand inputs include the equal-execution-time case.Source: §A.3 · pp. 58–59

Construction and feasible groups

  • Setting L = 6nA, b_i = L + a_i, and Bmax = B0 = nL + A makes a two-group schedule feasible exactly when EquiPartition has a solution.Every n+1 jobs exceed capacity, while any set of at most n−1 fits; a two-group schedule must therefore contain n jobs in each group, each consuming Bmax.Source: §A.3 · p. 58

Equal execution times

  • For equal execution times e_i = 1, execution contributes n(2n + 1), and the threshold distinguishes the partition schedule from every other grouping.A YES instance has a (n, n) schedule with recharge contribution nBmax; the proof uses L(n−1) > 5nA to separate other groupings.Source: §A.3 · p. 59

Energy equal to execution time

  • When e_i = b_i = L + a_i, a (n, n) schedule has recharge contribution n²L + nA, while every other grouping exceeds the decision threshold.The proof bounds the other-grouping cost strictly above Hprop using the chosen L and the bound on group sizes.Source: §A.3 · p. 59

A.4 Proof of Theorem T3 (𝑇max, Complete, 𝑏𝑖= 𝑏)

For equal energy demands under complete recharging, the proof reduces maximum tardiness to choosing group boundaries in EDF order. A dynamic program evaluates the maximum tardiness of each resulting group in O(n²) time.

EDF ordering and groups

  • The jobs are ordered by non-decreasing deadline, and a schedule partitions that EDF sequence into consecutive groups separated by complete recharges.Within each group there is no recharging; the first group may run from the initial charge without a preceding recharge.Source: §A.4 · pp. 59–60

Completion times and group costs

  • A group's completion times depend on its start position because cumulative recharge time before that position is independent of how preceding jobs were grouped.For a group beginning at position k, the proof expresses each completion using its execution-time prefix and R_k; the first group instead starts from B0 without recharging.Source: §A.4 · pp. 59–60

Dynamic-programming recurrence

  • The recurrence tries each possible start of the last group and combines its maximum tardiness with the best value for the preceding prefix, yielding O(n²) total time.Group costs are computed by extending each possible start one job at a time and updating maximum tardiness in O(1) per endpoint.Source: §A.4 · p. 60

A.5 Proof of Theorem T4 (𝑇max, Complete, NP-hard)

These proofs establish hardness transfers, dynamic programs for equal-demand cases, and structural tools for partition reductions. They also analyze subset-sum routines used to obtain the makespan approximation guarantee.

A.5 Proof of Theorem T4 (𝑇max, Complete, NP-hard)

  • Assigning every job deadline zero makes each job's tardiness equal its completion time, transferring makespan hardness to maximum tardiness.The polynomial map preserves each of the three execution-time/energy relationships in the source instances.Source: §A.5 · p. 60

A.6 Proof of Theorem T5 (𝑈, Complete, 𝑏𝑖= 𝑏)

  • For equal energy demands, an EDF-order dynamic program chooses a largest timely subset while tracking the completion time and battery after each timely job.It may append a job within the current group, recharge before a new group, or defer the job; retaining the earliest completion for each state is sufficient, and the algorithm runs in O(n³).Source: §A.6 · pp. 60–61

A.7 Proof of Lemma L8 (Optimal Schedule Structure) / A.8 Proof of Lemma L9 (Exact Cost Identity)

  • An optimal schedule can sort the prefix by e_i and the jobs after the separation job by e_i + b_i; the exact cost identity corrects the auxiliary cost by |δ|.The sorting exchanges preserve the separation job and position; the identity accounts for the extra recharge at the last left-block job and the anchor.Source: §A.7 · p. 61, §A.8 · p. 62

A.9 Proof of Lemma L11 (Anchor Position and Ties) / A.10 Proof of Lemma L12 (Only-If Direction)

  • In the chosen optimal schedule, the anchor is last in the prefix or immediately after the separation job; ties stay within the tail. A cost at most the threshold, given d≥T, K≥0, s≤2T, forces d=T, K=0, s=2T.Source: §A.9 · p. 62, §A.10 · p. 63

A.11 Proof of Theorem T19 (𝑈, Partial, Dynamic Program)

  • For partial recharging, the tardy-job dynamic program processes jobs in EDF order and tracks the last timely completion and remaining battery.For each job it compares deferring it with appending it to the timely sequence if it meets its deadline, accounting for any needed recharge.Source: §A.11 · p. 64

A.12 Subset-Sum Subroutines Used by 𝒜2

  • The makespan approximation uses two subset-sum routines: SS-MIN selects a low-energy head, while SS-MAX selects a high-energy final group.The routines classify and sort item weights to restrict the combinations considered.Source: §A.12 · p. 64, §A.12.1 · p. 64, §A.12.2 · p. 66

A.12.1 Minimum Head Energy

  • 5/4 is the approximation factor for SS-MIN, whose minimum-head routine runs in O(n log n) time.Its selected head's energy is bounded relative to the minimum, supporting the makespan bound when the same non-negative execution and charging terms are added.Source: §A.12.1 · pp. 65–66

A.12.2 Maximum Final-Group Energy

  • 3/4 is the approximation guarantee for SS-MAX: it returns a subset of at least 3C/4 weight or an optimal subset.The selected final group falls short of optimal energy by at most Bmax/4, bounding the additional recharging time used in the makespan guarantee.Source: §A.12.2 · p. 67
Loading 2610.02447v1…