Scheduling Tasks with Exponential Service Times on Nonidentical Processors to Minimize Various Cost Functions.

摘要

Preemptive scheduling of N tasks on m processors are considered; 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, 2nd shortest (longest) to the 2nd 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. (Author)