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 ℓ₁ 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/ε²)-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.