Scheduling a Sequence of Parallel Programs Containing Loops Within a Centralized Parallel Processing System
Zhen Liu, Don Towsley · 1992
We investigate the problem of scheduling a sequence of jobs running in a centralized parallel processing system with identical processors. The jobs represent parallel programs that contain probabilistic loops of tasks that can be simultaneously executed. We show that the Smallest Phase first policy is optimal within the class of nonpreemptive policies when the task processing times are identical and independently distributed random variables with an increasing likelihood ratio distribution. The optimality extends to the class of preemptive policies when the task processing times have an exponential distribution. The optimality is understood to be the stochastic minimization of the process of the numbers of jobs in the system and the minimization of mean response times of the jobs. Stronger optimality results on the minimization of job response time are obtained for a simpler job model.