Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions

Abstract

We consider preemptive scheduling of N tasks on m processors; processors have different speeds, tasks require amounts of work which are exponentially distributed, with different parameters. The policies of assigning at every moment the task with shortest (longest) expected processing time among those not yet completed to the fastest processor available, second shortest (longest) to the second fastest etc., are examined, and shown to minimize expected values of various cost functions. As special cases we obtain policies which minimize expected flowtime, expected makespan and expected lifetime of a series system with m component locations and N spares.