Improved Online Algorithm for Weighted Flow Time
Improved Online Algorithm for Weighted Flow Time
We discuss one of the most fundamental scheduling problem of processing jobs on a single machine to minimize the weighted flow time (weighted response time). Our main result is a O(log P)-competitive algorithm, where P is the maximum-to-minimum processing time ratio, improving upon the O(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> P)competitive algorithm …