abstract:  In this paper, we consider the problem of scheduling independent parallel tasks in parallel systems with identical processors.
The problem is NPhard,
since it includes the bin packing problem as a special case
when all tasks have unit execution time.
We propose and analyze a simple approximation algorithm called H_m,
where m is a positive integer.
Algorithm H_m has a moderate asymptotic worstcase performance ratio
in the range [1{2/3}..1{13/18}] for all m>=6;
but the algorithm has a small asymptotic worstcase performance ratio
in the range [1+1/(r+1)..1+1/r],
when task sizes do not exceed 1/r of the total available processors,
where r>1 is an integer.
Furthermore, we show that if the task sizes
are independent, identically distributed (i.i.d.) uniform random variables,
and task execution times are i.i.d. random variables
with finite mean and variance,
then the averagecase performance ratio of algorithm H_m
is no larger than 1.2898680...,
and for an exponential distribution of task sizes,
it does not exceed 1.2898305....
As demonstrated by our analytical as well as numerical results,
the averagecase performance ratio improves significantly
when tasks request for smaller numbers of processors.
