Semi-matching algorithms for scheduling parallel tasks under resource constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Semi-matching algorithms for scheduling parallel tasks under resource constraints

Résumé

We study the problem of minimum makespan scheduling when tasks are restricted to subsets of the processors (resource constraints), and require either one or multiple distinct processors to be executed (parallel tasks). This problem is related to the minimum makespan scheduling problem on unrelated machines, as well as to the concurrent job shop problem, and it amounts to finding a semi-matching in bipartite graphs or hypergraphs. While the problem was known to be NP-complete for bipartite graphs, but solvable in polynomial time for unweighted graphs (i.e., unit tasks), we prove that the problem is NP-complete for hypergraphs even in the unweighted case. We design several greedy algorithms of low complexity to solve two versions of the problem, and assess their performance through a set of exhaustive simulations. Even though there is no approximation guarantee on these linear algorithms, they return solutions close to the optimal (or a known lower bound) in average.
On étudie le problème d'ordonnancement visant à minimiser le temps d'exécution lorsque les tâches peuvent être exécutées soit sur un seul processeur, soit sur plusieurs processeurs en parallèle, et sont restreintes à cer- tains sous-ensembles de processeurs. Le problème se ramène à devoir trouver un couplage partiel dans un graphe biparti ou dans un hypergraphe. Sur les graphes bipartis, le problème général est NP-complet, mais il est possible de résoudre en temps polynomial les instances de problèmes où toutes les tâches sont de poids unitaire. Nous montrons dans ce rapport que le problème devient NP-complet pour les hypergraphes même dans le cas unitaire. Nous proposons plusieurs algorithmes gloutons pour résoudre deux versions du problème, et nous étudions leur performance à travers des simulations. Bien qu'il n'y ait aucune garantie d'approximation sur ces algorithmes, ils retournent en moyenne des so- lutions proches de l'optimal (ou d'une borne inférieure connue), avec un temps d'exécution très rapide.
Fichier principal
Vignette du fichier
rr-8089.pdf (786.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00738393 , version 1 (04-10-2012)
hal-00738393 , version 2 (24-10-2012)
hal-00738393 , version 3 (04-01-2013)
hal-00738393 , version 4 (18-04-2013)
hal-00738393 , version 5 (02-01-2014)

Identifiants

  • HAL Id : hal-00738393 , version 2

Citer

Anne Benoit, Johannes Langguth, Bora Uçar. Semi-matching algorithms for scheduling parallel tasks under resource constraints. [Research Report] RR-8089, 2012, pp.30. ⟨hal-00738393v2⟩

Collections

INRIA-RRRT
354 Consultations
387 Téléchargements

Partager

Gmail Facebook X LinkedIn More