In a scheduling problem, one is given a set of jobs with various processing time
s with the goal of
minimizing or maximizing some value given some constraints. I will be concerned
with stretch which is the ratio of a job's completion time
to its processing time. This metric, which has only been looked at recently, se
ems useful because it measures a schedule's success with respect to
the size of the job being requested. In particular I am interested in online (j
obs have various release times which the scheduler does not know
about), nonclairvoyant (the size of a job is not known until it is completed) sc
hedules with the goal of minimizing the max stretch on all jobs
scheduled.
