Improved Scheduling with a Shared Resource

We consider the following shared-resource scheduling problem: Given a set of jobs J, for each \(j\in J\) we must schedule a job-specific processing volume of \(v_j>0\) . A total resource of 1 is available at any time. Jobs have a resource requirement \(r_j\in \left[ 0,1 \right] \) , and the resources assigned to them may vary over time. However, assigning them less will cause a proportional slowdown. We consider two settings. In the first, we seek to minimize the makespan in an online setting: The resource assignment of a job must be fixed before the next job arrives. Here we give an optimal \(e/(e-1)\) -competitive algorithm with runtime \(\text {O}({n\text {\,\,} \log \, n})\) . In the second, we aim to minimize the total completion time. We use a continuous linear programming (CLP) formulation for the fractional total completion time and combine it with a previously known dominance property from malleable job scheduling to obtain a lower bound on the total completion time. We extract structural properties by considering a geometrical representation of a CLP’s primal-dual pair. We combine the CLP schedule with a greedy schedule to obtain a \((3/2+\varepsilon )\) -approximation for this setting. This improves upon the so far best-known approximation factor of 2.