Efficient approximation method optimizes task loads on few machines
An EPTAS for Offline Temporary Tasks Assignment on Few Machines
Data Structures and AlgorithmsComputational Complexity
Summary
Assigning temporary jobs to machines so none get overloaded can be hard, especially when jobs last different times and have different importance. The authors found a way to get very close to the best job assignment quickly when the number of machines is fixed. They showed their method runs much faster than older ones and proved that no perfect fast method likely exists. Their approach simplifies the problem by grouping jobs and carefully tracking assignments over time.
What this means in practice
- •For data center operators: Assign temporary workloads to few servers efficiently to avoid overload and minimize peak usage.
- •For manufacturing floor managers: Schedule temporary machine tasks to balance load and avoid bottlenecks with near-optimal task assignments.
A theory result. No direct application yet.
Authors
Junho Hwang
Abstract
In offline temporary tasks assignment, each job has a time interval and a positive weight and is assigned to one of $r$ identical machines for its entire interval; the goal is to minimize the peak load, the largest total weight of jobs that are simultaneously active on one machine. For every fixed $r$, we give an efficient polynomial-time approximation scheme (EPTAS) with running time $f(r,1/\varepsilon)\cdot N^{O(1)}$, where $N$ is the input length. The previous approximation scheme, by Azar, Regev, Sgall, and Woeginger (2002), runs in time $n^{O(r^3\log r/\varepsilon^3)}$ on $n$ jobs. We also show that for every fixed $r\ge2$ the problem is strongly NP-hard, so it has no FPTAS unless P=NP, and that under the Exponential Time Hypothesis no deterministic $(1+\varepsilon)$-approximation runs in time $2^{o(1/\varepsilon)}\cdot N^{O(1)}$. The key idea is to bound the loads of each group of simultaneously active jobs by a few weighted intervals whose positions are fixed in advance; a dynamic program over the time line then only has to record which machine carries each interval.