Minimizing Weighted Mean Completion Time for Malleable Tasks Scheduling
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| dc.contributor.author | BONICHON, Nicolas | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | EYRAUD-DUBOIS, Lionel | |
| hal.structure.identifier | Laboratoire de l'Informatique du Parallélisme [LIP] | |
| hal.structure.identifier | Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA] | |
| dc.contributor.author | MARCHAL, Loris | |
| dc.contributor.editor | IEEE | |
| dc.date.accessioned | 2024-04-15T09:46:52Z | |
| dc.date.available | 2024-04-15T09:46:52Z | |
| dc.date.created | 2011-09-30 | |
| dc.date.issued | 2012 | |
| dc.date.conference | 2012-05 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198046 | |
| dc.description.abstractEn | Malleable tasks are jobs that can be scheduled with preemptions on a varying number of resources. We focus on the special case of work-preserving malleable tasks, for which the area of the allocated resources does not depend on the allocation and is equal to the sequential processing time. Moreover, we assume that the number of resources allocated to each task at each time instant is bounded. We consider both the clairvoyant and non-clairvoyant cases, and we focus on minimizing the weighted sum of completion times. In the weighted non-clairvoyant case, we propose an approximation algorithm whose ratio (2) is the same as in the unweighted non-clairvoyant case. In the clairvoyant case, we provide a normal form for the schedule of such malleable tasks, and prove that any valid schedule can be turned into this normal form, based only on the completion times of the tasks. We show that in these normal form schedules, the number of preemptions per task is bounded by 3 on average. At last, we analyze the performance of greedy schedules, and prove that optimal schedules are greedy for a special case of homogeneous instances. We conjecture that there exists an optimal greedy schedule for all instances, which would greatly simplify the study of this problem. Finally, we explore the complexity of the problem restricted to homogeneous instances, which is still open despite its simplicity. | |
| dc.description.sponsorship | Simulation extrêmement extensible avec SimGrid - ANR-08-SEGI-0022 | |
| dc.language.iso | en | |
| dc.subject.en | Scheduling | |
| dc.subject.en | Independent Tasks Scheduling | |
| dc.subject.en | Approximation Algorithms | |
| dc.subject.en | Non Clairvoyant Algorithms | |
| dc.subject.en | Weighted Mean Completion Time | |
| dc.subject.en | Malleable Tasks | |
| dc.title.en | Minimizing Weighted Mean Completion Time for Malleable Tasks Scheduling | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | IPDPS 2012, 26th IEEE International Parallel & Distributed Processing Symposium | |
| bordeaux.country | CN | |
| bordeaux.conference.city | Shangai | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00564056 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00564056v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2012&rft.au=BEAUMONT,%20Olivier&BONICHON,%20Nicolas&EYRAUD-DUBOIS,%20Lionel&MARCHAL,%20Loris&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||