Pareto-Optimal Scheduling in the Half-batch Multiserver-job Model
2026-07-10 • Performance
Performance
AI summaryⓘ
The authors study a system where big jobs need all servers at once and small jobs need just one server each, with big jobs arriving randomly. They create a model called the half-batch MSJ to understand how to balance fast finishing times for big jobs and high throughput for small jobs. They find an exact and simple way to describe the best trade-offs between these goals using a set of rules called convoy policies. These results apply broadly, no matter the arrival rate, number of servers, or job sizes. Essentially, the authors show how to schedule jobs to balance speed and capacity in these mixed job settings.
queueing modelPoisson processmultiserver jobslatency-sensitivethroughputPareto frontierconvoy policymean response timejob schedulinglarge-scale computing
Authors
Ziyuan Wang, Izzy Grosof
Abstract
In large-scale computing systems, jobs often demand heterogeneous server allocations: large jobs that occupy a substantial fraction of the servers are of high importance and are thus latency-sensitive, while small jobs fill in the remaining capacity to maintain throughput. To model this dynamic, we introduce the half-batch multiserver-job (MSJ) framework, a queueing model in which large jobs arrive according to a Poisson process and require all servers simultaneously, while small jobs, each needing only one server, are always available. We prove that, in the half-batch MSJ model, the Pareto frontier for large-job mean response time and small-job throughput admits a simple and exact characterization. It is generated by a family of convoy policies, under which the system serves small jobs until $k$ large jobs have arrived and then switches to serving large jobs, together with convex combinations of neighboring convoy policies. Our result is fully general and non-asymptotic, holding for every stable arrival rate $λ$, every number of servers $n$, and every large-job size distribution $S$.