Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes

Modern computing workloads are often composed of parallelizable jobs. A parallelizable job can be completed more quickly when run on additional servers. However, each job can only use a limited number of servers, known as its parallelizability level, which is determined by the type of computation the job performs and how it is implemented. Workloads generally consist of multiple job classes, where jobs from different classes have different parallelizability levels and follow different job size (service requirement) distributions. This paper considers scheduling parallelizable jobs belonging to an arbitrary number of job classes. Given a limited number of servers, we must allocate servers across a stream of arriving jobs to minimize mean response time—the average time from when a job arrives to the system until it completes. We find that in lighter-load scaling regimes (i.e., sub-Halfin-Whitt), the optimal allocation policy is least-parallelizable-first, which prioritizes jobs from the least parallelizable job classes regardless of their size distributions. By contrast, we find that in the heavier-load regimes (i.e., super-nondegenerate slowdown), the optimal allocation policy prioritizes jobs with the shortest expected remaining processing time. We also develop policies that are asymptotically optimal when the scaling regime is not known a priori. Funding: Open Access funding was provided by the University of North Carolina at Chapel Hill. This work was supported by the National Science Foundation (NSF) [Grants NSF-CIF-2403194, NSF-CCF-2403195, NSF-III-2322973, NSF-IIS-2322974, and NSF-CMMI-2307008]. W. Wang is supported in part by the NSF [Grants ECCS-2145713, CCF-2428569, and ECCS-2432545]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/stsy.2024.0084 .