Worst case bounds for independent task scheduling

The problem of assigning N independent tasks to p processors is addressed. Worst case scheduling bounds for general list-algorithms are derived and the special case of the Longest-Processing-Time-First algorithm is treated in more detail. It is shown that under modest assumptions concerning the tasklength distribution, all list schedulers will generate asymptotically optimal results when the number of tasks grows indefinitely. The bounds are illustrated by simulation results for fixed and variable tasklengthsThe problem of assigning N independent tasks to p processors is addressed. Worst case scheduling bounds for general list-algorithms are derived and the special case of the Longest-Processing-Time-First algorithm is treated in more detail. It is shown that under modest assumptions concerning the tasklength distribution, all list schedulers will generate asymptotically optimal results when the number of tasks grows indefinitely. The bounds are illustrated by simulation results for fixed and variable tasklengthsC