arXiv preprint ·
Job Scheduling with Battery Recharging Constraints
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sparsification Framework for Directed Densest Subgraph
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Faster Auction Algorithm for Weighted Matroid Intersection
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.