An Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time on Unrelated Machines
Sungjin Im, Benjamin Moseley · 2011
We consider the problem of scheduling jobs that arrive online in the unrelated machine model to minimize ℓk norms of weighted flowtime. In the unrelated setting, the processing time and weight of a job depends on the machine it is assigned to, and it is perhaps the most general machine model considered in scheduling literature. Chadha et al. [10] obtained a recent breakthrough result in obtaining the first non-trivial algorithm for minimizing weighted flowtime (that is, the ℓ1 norm) in this very general setting via a novel potential function based analysis. They described a simple algorithm and showed that for any ε > 0 it is (1 + ε)-speed O(1/ε2)-competitive (a scalable algorithm). In this paper we give the first non-trivial and scalable algorithm for minimizing ℓk norms of weighted flowtime in the unrelated machine model; for any ε > 0, the algorithm is O(k/ε2+2/k)-competitive. The algorithm is immediate-dispatch and non-migratory. Our result is of both practical and theoretical interest. Scheduling to minimize ℓk norms of flowtime for some small k > 1 has been shown to balance total response time and fairness, which is desirable in practice. On the theoretical side, ℓk norms for k > 1 pose substantial technical hurdles when compared to when k = 1 even for the single machine case. Our work develops a novel potential function as well as several tools that can be used to lower bound the optimal solution.