Tight Approximation for Scheduling Parallel Job on Identical Clusters

Marin Bougeret 1, * Pierre-Francois Dutot 2, 3 Denis Trystram 2, 4 Klaus Jansen 5 Christina Robenek 5
* Auteur correspondant
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
5 Theory of Parallelism
Department of Computer Science
Abstract : 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$.
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

Contributeur : Marin Bougeret <>
Soumis le : jeudi 5 janvier 2012 - 09:55:28
Dernière modification le : jeudi 11 octobre 2018 - 08:48:03
Document(s) archivé(s) le : vendredi 6 avril 2012 - 02:26:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : lirmm-00656780, version 1


Marin Bougeret, Pierre-Francois Dutot, Denis Trystram, Klaus Jansen, Christina Robenek. Tight Approximation for Scheduling Parallel Job on Identical Clusters. RR-12001, 2012. 〈lirmm-00656780〉



Consultations de la notice


Téléchargements de fichiers