An EPTAS for Vector Scheduling with Time Intervals

Abstract

We study vector scheduling in which each job is active during a fixed time interval. A job uses several resources and stays on one machine for its entire interval; its resource requirements may depend on the machine. The objective is to minimize the largest resource load over all machines and times. For $r$ machines and $d$ resources, we give a deterministic $(1+\epsilon )$-approximation in $f(r,d,1/\epsilon )N^{O(1)}$ time, where $N$ is the binary input length. This gives an efficient polynomial-time approximation scheme for fixed $r$ and $d$, extending approximation schemes for scalar temporary tasks assignment. The algorithm merges jobs into blocks whose time intervals are fixed before any machine is chosen, and assigns the blocks by dynamic programming over a balanced recursive split of the time line. We also prove strong NP-hardness and an exponential lower bound in $1/\epsilon$ under the Exponential Time Hypothesis, already for two identical machines and one resource.

arXiv comment18 pages, 4 figures. v2: extended to several resources and unrelated machines, with a new title and simplified proofs