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(sqrt{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+epsilon)approximation algorithm for the preemptive and the nonpreemptive case of minimizing weighted flow time on m machines with a running time of f(k,epsilon,m)* n^{O(1)}, i.e., our combined parameters are k,epsilon, 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.
BibTeX  Entry
@InProceedings{wiese:LIPIcs:2018:9432,
author = {Andreas Wiese},
title = {{FixedParameter Approximation Schemes for Weighted Flowtime}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {28:128:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9432},
URN = {urn:nbn:de:0030drops94326},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.28},
annote = {Keywords: Scheduling, fixedparameter algorithms, approximation algorithms, approximation schemes}
}
Keywords: 

Scheduling, fixedparameter algorithms, approximation algorithms, approximation schemes 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 