Why the mean is inadequate for accurate scheduling decisions

In a distributed environment, the generalized scheduling problem attempts to optimize some performance criteria by assigning tasks to resources and by determining the order in which those tasks will be executed. Although most resource management systems in use today have the goal of maximizing the use of idle processors, several, such as LSF and SmartNet attempt to minimize the time at which the last job, in each set of jobs, completes. They attempt to deliver better quality of service to jobs by using scheduling heuristics that calculate schedules based upon the expected run-times of each job on each machine. This paper analyzes an exhaustive scheduling algorithm that minimizes the time at which the last job completes, if all jobs execute for exactly their expected run-limes. The authors show that if this assumption is violated, that is, if jobs do not execute for exactly their expected run-times, then this algorithm will underestimate the time at which the last job is exacted to finish, sometimes substantially. The authors conclude that an algorithm that uses not only the expected run-times, but also their distributions, can obtain better schedules