Theory of Computing
-------------------
Title     : Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor
Authors   : Chandra Chekuri, Sungjin Im, and Benjamin Moseley
Volume    : 8
Number    : 7
Pages     : 165-195
URL       : https://theoryofcomputing.org/articles/v008a007

Abstract
--------

  This paper presents several online scheduling algorithms for two
  related performance metrics, namely maximum response time and
  maximum delay-factor, and also their weighted versions. The delay
  factor metric is new (introduced in Chang et al. (SODA'08)), while
  special cases of maximum weighted response time have been considered
  before.  We study both the standard scheduling model where each
  arriving job requires its own processing, as well as the broadcast
  scheduling model where multiple requests/jobs can be simultaneously
  satisfied.

  Motivated by strong lower bounds, we consider the resource
  augmentation model introduced in Kalyanasundaram and Pruhs
  (JACM'95) where the algorithm is given a machine with faster
  speed than the adversary. We give scalable algorithms; that is,
  algorithms that when given (1+epsilon)-speed are
  O(poly(1/epsilon))-competitive for any fixed epsilon > 0. Our
  main contributions are for broadcast scheduling.  Along the way
  we also show that the FIFO (first-in-first-out) algorithm is
  2-competitive for broadcast scheduling even when pages have
  non-uniform sizes. We complement our algorithmic results by
  showing that a natural greedy algorithm modeled after LWF
  (Longest-Wait-First) is, for any s >= 1, not constant competitive
  for minimizing maximum delay factor when given an s-speed
  machine. The lower bound holds even in the restricted setting of
  standard scheduling of jobs with uniform size, and demonstrates
  the importance of the trade-off made in our algorithms.