Fixed-Parameter approximation schemes for weighted flowtime

Abstract

Given a set of n jobs with integral release dates, processing times and weights, it is a natural and important scheduling problem to compute a schedule that minimizes the sum of the weighted flow times of the jobs. There are strong lower bounds for the possible approximation ratios. In the nonpreemptive case, even on a single machine the best known result is a O( √ n)-approximation which is best possible. In the preemptive case on m identical machines there is a O(log min{ n m , P})- approximation (where P denotes the maximum job size) which is also best possible. We study the problem in the parametrized setting where our parameter k is an upper bound on the maximum (integral) processing time and weight of a job, a standard parameter for scheduling problems. We present a (1 + )-approximation algorithm for the preemptive and the non-preemptive case of minimizing weighted flow time on m machines with a running time of f(k, , m)·n O(1), i.e., our combined parameters are k, , and m. Key to our results is to distinguish time intervals according to whether in the optimal solution the pending jobs have large or small total weight. Depending on this we employ dynamic programming, linear programming, greedy routines, or combinations of the latter to compute the schedule for each respective interval.