Tight Approximation for Scheduling Parallel Job on Identical Clusters
Résumé
In the grid computing paradigm, several clusters share their computing resources in order to distribute the workload. Each of the $N$ cluster is a set of $m$ identical processors (connected by a local interconnection network), and $n$ parallel jobs are submitted to a centralized queue. A job $J_j$ requires $q_j$ processors during $p_j$ units of time. We consider the Multiple Cluster Scheduling Problem ($\MCSP$), where the objective of is to schedule all the jobs in the clusters, minimizing the maximum completion time (makespan). This problem is closely related to the multiple strip packing problem, where the objective is to pack $n$ rectangles into $m$ strips of width $1$, minimizing the maximum height over all the strips. $\MCSP$ is $2$-inapproximable (unless $P=NP$), and several approximation algorithm have been proposed. However, ratio $2$ has only been reached by algorithms that use extremely costly and complex subroutines as "black boxes" (for example area maximization subroutines on a constant ($\approx 10^4$) number of bins, of $PTAS$ for the classical $P||C_{max}$ problem). Thus, our objective is to find a reasonable restriction of $\MCSP$ where the inapproximability lower bound could be tightened in almost linear time. In this spirit we study a restriction of $\MCSP$ where jobs do not require strictly more than half of the processors, and we provide for this problem a $2$-approximation running in $O(log_2(nh_{max})n(N+log(n)))$, where $h_{max}$ is the maximum processing time of a job. This result is somehow optimal, as this restriction of $\MCSP$ (and even simpler ones, where jobs require less than $\frac{m}{c}$, $c \in \mathbb{N}, c \ge 2$) remain $2$-innapproximable unless $\P=\NP$.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...