Craig Bowles

Project: Non-Clairvoyant Job Scheduling
School: Cornell University


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.