Scheduling to Maximize Weighted Throughput with an Active-Time Budget
Data Structures and Algorithms
Summary
The authors study a scheduling problem where jobs have weights, deadlines, and need to be scheduled in limited active time slots, aiming to maximize the total weight of completed jobs. They explore the problem's difficulty, showing it is NP-hard in general and cannot be approximated very closely unless P = NP. For certain special types of job intervals, they provide exact algorithms that run efficiently depending on parameters like the number of active slots and processors. Their work generalizes the classical problem of minimizing active time to weighted throughput maximization under an active time constraint.
Authors
Susanne Albers, G. Wessel van der Heijden
Abstract
We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.