Pareto-Optimal Scheduling in the Half-batch Multiserver-job Model
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.
Related
- Optimal Uniform-like Scheduling of Maintenance
- Pareto-Optimal Hypersonic Vehicle Design with Canonical-Coordinate Neural Operator Surrogates Under Ablation-Driven Shape Change and Incidence Variation
- Dropout Universality: Scaling Laws and Optimal Scheduling at the Edge-of-Chaos
- DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
- Expected Batch Optimal Transport Plans and Consequences for Flow Matching
BibTeX
@misc{wang2026paretooptimal,
title = {{Pareto-Optimal Scheduling in the Half-batch Multiserver-job Model}},
author = {Ziyuan Wang and Izzy Grosof},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.08999},
eprint = {2607.08999},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.08999},
}
RIS
TY - UNPB
TI - Pareto-Optimal Scheduling in the Half-batch Multiserver-job Model
AU - Ziyuan Wang
AU - Izzy Grosof
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2607.08999
UR - https://arxiv.org/abs/2607.08999
AB - 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.
ER -