Scheduling battery-powered devices with recharge time constraints
Job Scheduling with Battery Recharging Constraints
Data Structures and Algorithms
Summary
Battery-powered devices like delivery drones must recharge between tasks, which delays their work. The authors study how to schedule jobs when recharge time depends on how much energy is needed, not just a fixed duration. They explore different ways of recharging, whether partially or fully, and analyze how hard it is to find the best schedule. They also offer approximation methods when exact solutions are too complex. Their work helps understand and plan recharge and job timing better for devices limited by battery energy.
What this means in practice
- •For drone fleet operators: Optimize delivery drone task schedules when recharge times vary with battery energy needed, improving operational efficiency.
- •For robotics system designers: Design scheduling systems that handle variable recharge durations to better manage energy constraints in battery-powered robots.
Authors
Rudransh Kumar, Nima Nasiri, Jared Paul, Sathish Gopalakrishnan
Abstract
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.