Source-linked AI summary
Scheduling to Maximize Weighted Throughput with an Active-Time Budget
Susanne Albers, G. Wessel van der Heijden
TL;DR
The paper asks how to maximize the weight of completed jobs under a limited active-time budget, generalizing active-time minimization to arbitrary processing times. It develops hardness, approximation, structural, and exact algorithmic results across interval families, including exact algorithms for proper and laminar intervals. The results establish NP-hardness and no FPTAS for general unbounded-capacity intervals, alongside an Ω(1/ log K)-approximation and parameterized exact algorithms for structured windows.
Problem
The problem is to maximize the total weight of completed jobs using at most K active time slots, a weighted-throughput setting that extends active-time minimization and arbitrary processing times beyond prior unit-job work.
Method
The paper analyzes general, proper, and laminar interval families using hardness reductions, processing-time grouping, a canonical-ordering lemma, and dynamic programming over capacity profiles.
Results
General intervals with m = ∞ are NP-hard and admit no FPTAS unless P = NP, while achieving an Ω(1/ log K)-approximation; proper and laminar intervals have exact parameterized algorithms.
Takeaways & Limitations
The study provides a complexity and algorithmic map for weighted active-time scheduling, distinguishing difficult general intervals from structured proper and laminar cases.
Takeaways & Limitations
For unbounded capacity, whether the Ω(1/ log K)-approximation can be improved remains open, and polynomial-time algorithms for proper or laminar intervals are unresolved.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper formulates weighted-throughput maximization under an active-time budget and systematically studies its complexity and algorithms across interval structures. It establishes hardness and approximation results for general intervals, plus exact algorithms for proper and laminar intervals.
- Problem setting: An active-time budget K limits the slots used, while the objective maximizes the total weight of completed jobs; partial jobs contribute nothing.The model generalizes active-time minimization, which is recovered by testing whether all jobs can be completed within K active slots.
- Motivation and gap: The weighted-throughput variant with arbitrary processing times had remained largely unexplored, extending prior throughput work focused on unit-processing-time jobs.Related work identifies this setting as an open research direction.
- Results: For general intervals with unbounded parallelism, the problem is NP-hard, has no FPTAS unless P = NP, and admits an Ω(1/ log K)-approximation in polynomial time in n and K.The approximation groups jobs by processing time.
- Results: For proper intervals, a canonical-ordering lemma yields an exact (nK)O(m)-time algorithm, which is XP parameterized by capacity m.The structural result bounds the number of split jobs across any time-slot boundary by 2m−1.
- Results: For laminar intervals, a dynamic program over capacity profiles gives an exact f(K, m) · nO(1)-time algorithm parameterized by K and m.Laminar windows are nested or disjoint, enabling the capacity-profile dynamic program.
2 General intervals with unbounded parallelism
For general intervals with unbounded parallelism, weighted throughput scheduling is computationally difficult, but admits a pseudo-polynomial logarithmic approximation. The approach compresses the time horizon, reduces hardness from MaxDiCut on DAGs, and groups jobs by processing time for approximation.
- Hardness: Overlapping job windows make the active-time cost depend on shared slot locations rather than fixed per-job costs.This interaction distinguishes the problem from 0/1 knapsack and underlies the reduction's difficulty.
- Hardness: NP-hardness holds even with unbounded parallelism, and no FPTAS exists unless P = NP.The hardness reduction is from maximum directed cut on acyclic digraphs; integer solution values allow an FPTAS to solve the NP-hard decision problem exactly.
- Time-horizon compression: O(nK) candidate slots suffice after restricting attention to K slots around release-time and deadline breakpoints.This yields algorithms polynomial in n and the numeric value of K.
- Approximation: For a bucket q, each center opens a 2q-slot block, and every job hit by that center can be completed within its window.Lemma 2 guarantees at least p_j slots of the block intersect each hit job's window, while Lemma 3 gives a constant-factor value guarantee for the greedy bucket algorithm.
- Approximation: Large jobs admit a contiguous K-slot representation because their feasible intervals share a common slot under the Helly property.Replacing active slots toward the common slot preserves the number of usable slots in every selected job window.
- Approximation: Ω(1/log K)-approximation is obtained by grouping jobs into processing-time buckets and retaining the best bucket schedule.Regular buckets receive a constant-factor greedy solution, while the large bucket is solved optimally; there are O(log K) buckets.
3 Proper intervals with parameterized m
For proper intervals, canonical schedules limit boundary-crossing jobs, enabling an exact dynamic program with running time (nK)O(m).
- Structural setup: Proper intervals allow jobs to be indexed so release times and deadlines are both nondecreasing.The algorithm discards jobs with pj > K and considers schedules that process jobs only when they complete.
- Canonical schedules: Every feasible schedule can be transformed without changing active slots or completed jobs into a canonical schedule with no inversion pairs.An inversion swaps units between two jobs while preserving capacities, windows, active slots, and completed jobs.
- Boundary structure: At most 2m −1 jobs are split across any boundary in a canonical schedule.If at least 2m jobs were split, the crossing rule would force a post-boundary slot to contain at least m + 1 jobs, contradicting capacity m.
- Boundary structure: Accepted live jobs that are not split are separated by a single index cut, with earlier-index jobs scheduled before the boundary and later-index jobs after it.Otherwise, scheduling a later-index job after the boundary and an earlier-index job before it would create an inversion pair.
- Result: Weighted throughput maximization on proper intervals is solvable exactly in (nK)O(m) time, and is XP in m.The algorithm is pseudo-polynomial in K.
4 An FPT algorithm for laminar intervals with weighted throughput
For laminar intervals, a bottom-up dynamic program combines nested subwindows through bounded capacity profiles and solves weighted throughput exactly in f(K,m)·nO(1) time.
- Laminar structure: Laminar windows are pairwise disjoint or nested, forming a rooted forest whose children are pairwise disjoint maximal subwindows.A dummy root connects the roots of the laminar forest.
- Tree dynamic program: The algorithm processes the laminar tree bottom-up and reserves private slots available to jobs at a node or its ancestors.Private regions exclude all child windows, and no more than K slots are reserved.
- Capacity profiles: A capacity profile is a histogram recording how many active slots have each residual capacity from 0 through m.The profile uses at most K active slots, so slot identities are unnecessary for ancestor jobs.
- Transitions: For each job, the dynamic program either rejects it or places its pj units in pj distinct active slots within its window, adding wj when accepted.Choosing slots with positive residual capacity preserves the per-slot capacity and one-unit-per-slot constraints.
- Result: Weighted-throughput active-time scheduling on laminar intervals is solvable exactly in f(K, m)·nO(1) time and is FPT parameterized by K and m.Every considered profile uses at most K active slots.
- Correctness: The dynamic program constructs feasible schedules and represents every feasible schedule, so its maximum table value is optimal.Accepted jobs receive exactly pj units inside their windows, while rejected jobs contribute no weight.
5 Conclusion and Future Work
The paper establishes hardness and approximation barriers for weighted-throughput active-time scheduling, while providing exact algorithms for structured interval families. It closes by identifying improvements to the approximation and parameterized algorithms as open questions.
- Unbounded capacity is NP-hard, has no FPTAS unless P = NP, and admits an Ω(1/ log K)-approximation.
- Proper intervals admit a pseudo-polynomial (nK)O(m)-time algorithm, while laminar intervals admit an FPT algorithm parameterized by K and m.
- Improving the Ω(1/ log K)-approximation for unbounded capacity remains open.
- Whether proper or laminar intervals have polynomial-time algorithms or fixed-parameter algorithms with smaller parameter sets remains unresolved.
A Interval-ordered chains and NP-hardness
The appendix reduces Balanced SAT to makespan minimization for interval-ordered chains with unit-time jobs. Variable, clause, copy, and filler gadgets encode assignments and clauses, yielding NP-hardness through a threshold-makespan equivalence.
- Model: IOC consists of unit-time jobs partitioned into ordered chains, with precedence constraints between chains induced by an interval order.
- Reduction: The reduction starts from Balanced SAT, requiring a satisfying assignment with exactly n/2 variables set true, and targets makespan τ.
- Gadgets: Variable gadgets place each literal occurrence in two consecutive slots, and choosing one slot represents the truth value of the variable.
- Gadgets: Clause gadgets use a clause slot and literal-specific intervals, while filler sets control capacity at clause and boundary slots.
- Gadgets: Copy gadgets ensure that occurrences of each variable in different clauses receive the same value.
- Hardness proof: The constructed instance has critical-path length τ = k + 2 + Pk i=1 ni, and the Balanced SAT formula is balanced-satisfiable if and only if makespan at most τ is feasible.