View article

We consider the scheduling problem of n independent jobs on m identical parallel processors in order to minimize makespan, the completion time of the last job. We propose a new approximation algorithm that iteratively combines partial solutions to the problem. The worst‐case performance ratio of the algorithm is , where z is the number of initial partial solutions that are obtained by partitioning the set of jobs into z families of subsets which satisfy suitable properties. The computational behavior of our worst‐case performance ratio provided encouraging results on three families of instances taken from the literature.