Scheduling Independent Tasks to Minimize

the Makespan on Identical Machines

TR 94-13

Abstract

In this paper we consider scheduling n tasks with task times that are
i.i.d. random variables with a common distribution function F on m
parallel machines. Scheduling is done by an a priori assignment of
tasks to processors. We show that if the distribution function F is a
P?lya frequency function of order 2 then the assignment which
attempts to place an equal number of tasks on each processor
achieves the stochastically smallest makespan among all assignments.
The condition embraces many important distributions, such
as the gamma and truncated normal distributions.

November 1, 1993

Department of Computer Science
The University of Arizona
Tucson, AZ 85721

John Bruno1
AT&T Bell Laboratories
600 Mountain Avenue
Murray Hill, NJ 07974

Edward G. Coffman, Jr.
AT&T Bell Laboratories
600 Mountain Avenue
Murray Hill, NJ 07974

Peter Downey
Department of Computer
Science
University of Arizona
Tucson, AZ 85721

1. Currently on sabbatical from the Department of Computer Science, University of California, Santa Barbara. The work of this author was partially supported by a UC MICRO Grant and by the Xerox Corporation.