Master's thesis, University of Illinois at Urbana-Champaign, December 2002.
My advisor was Jeff Erickson.
Download as gzipped postscript or pdf
This thesis includes work published independently as SPT is Optimally Competitive for Uniprocessor Flow. That version should be read in preference to this one for the common material because the referees have greatly improved the presentation and pointed out a flaw in one of the proofs, which was fixed in that paper.
We address the scheduling problem of minimizing total flow. Our primary focus is on the online setting. We begin by showing a structural similarity between the uniprocessor Shortest Remaining Processing Time (SRPT) and Shortest Processing Time (SPT) schedules. This structural result leads to a proof that SPT is (Δ+1)/2-competitive for nonpreemptive uniprocessor total flow, where Δ is the ratio between the longest and shortest job durations. This competitive ratio improves on the ratio of Δ+1 previously shown by Epstein and van Stee as a special case of their work on a resource-augmented version of the problem. The same technique leads us to an O(Δ log min{n,Δ})-competitive algorithm for nonpreemptive multiprocessor total flow, the first competitive algorithm known for this problem. Then we show that (Δ+1)/2 and (Δ+6)/8 are lower bounds on the competitive ratio of deterministic and randomized busy algorithms, respectively. (A busy algorithm is one that is not unnecessarily idle.) Since SPT is a busy deterministic algorithm, it is the most competitive among deterministic algorithms and cannot be much less competitive than the best randomized busy algorithm.
We also briefly consider offline scheduling. In this setting, we show that total flow cannot be approximated to a factor of n1-ε or Δ1-ε for any constant ε > 0 unless P=NP. The proof of this result closely follows the uniprocessor approximability lower bound of n1/2-ε by Kellerer et al. and the multiprocessor bound of n1/3-ε by Leonardi and Raz, neither of which are restricted to busy algorithms.