Improved approximation algorithms for scheduling parallel jobs on identical clusters

The Multiple Cluster Scheduling Problem corresponds to minimizing the maximum completion time (makespan) of a set of n parallel rigid (and non-preemptive) jobs submitted to N identical clusters. It cannot be approximated with a ratio better than 2 (unless P = NP ). We present in this paper the methodology that encompasses several existing results [1, 2]. We detail first how to apply it for obtaining a 5 2 -approximation. Then, we use it to provide a new 7 3 -approximation running in O ( log ⁡ ( n h max ) N ( n + log ⁡ ( n ) ) ), where h max is the processing time of the longest job. Finally, we apply it to a restriction of the problem to jobs of limited size, leading to a 2-approximation which is the best possible ratio since the restriction remains 2-inapproximable.

Authors

• Marin Bougeret
• Pierre-Francois Dutot
• Denis Trystram
• Klaus Jansen
• Christina Robenek

Keywords

• Scheduling
• Parallel job
• Strip packing
• Approximation algorithm