Scheduling with an Orthogonal Resource Constraint

We address a scheduling problem that arises in highly parallelized environments like modern multi-core CPU/GPU computer architectures where simultaneously active jobs share a common limited resource, e.g., memory cache. The scheduler must ensure that the demand for the common resource never exceeds the available capacity. This introduces an orthogonal constraint to the classical minimum makespan scheduling problem. Such a constraint also arises in other contexts where a common resource is shared across machines.

We study the non-preemptive case of this problem and present a (2+ϵ)-approximation algorithm which relies on the interplay of several classical and modern techniques in scheduling like grouping, job-classification, and the use of configuration-LPs. This improves upon previous bound of 3 that can be obtained by list scheduling approaches, and gets close to the (3/2−ϵ) inapproximability bound. If the number of machines or the number of different resource requirements are bounded by a constant we obtain a polynomial time approximation scheme.