Improved scheduling algorithms boost job throughput on identical machines
Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization
Data Structures and Algorithms
Summary
This paper looks at how to schedule as many jobs as possible on machines when each job has a specific time window to run and cannot be paused once started. The authors develop new algorithms that do better than previous ones in choosing which jobs to run so more get completed on time. Their methods handle many machines and use clever ways to divide time and coordinate job assignments. The improvements come from better mathematical models that carefully handle job overlaps and timing constraints.
What this means in practice
- •For data center operators: Improve job throughput on multiple identical servers by scheduling tasks more efficiently within given deadlines and start times.
- •For manufacturing plant schedulers: Optimize machine job assignments to maximize completed jobs without interruptions, reducing idle time in production lines.
A theory result. No direct application yet.
Authors
Weitian Tong, Yao Xu
Abstract
We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.