Scheduling jobs on heterogeneous platforms

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

hal-00738508, version 1

Scheduling jobs on heterogeneous platforms

Marin Bougeret () ¹, Pierre-Francois Dutot ()^a^, 2, 3, Klaus Jansen ⁴, Christina Robenek ⁴, Denis Trystram ()^b^, 2, 5

COCOON (2011) unkown

Résumé : In the context of grid scheduling we consider a scheduling scenario, where parallel jobs have to be scheduled non-preemptively on heterogeneous computational platforms of processors. The speed of the processors may differ among the platforms and the jobs are submitted si- multaneously or over the time and cannot run across multiple platforms. We focus on the target of minimizing the total makespan, i.e. the global latest finishing time of a job. In this paper we present an AFPTAS for the problem without release times and show how to generalize our result to malleable jobs and jobs with release times.

a – Université Pierre Mendès-France - Grenoble II
b – Grenoble INP
1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
CNRS : UMR5506 – Université Montpellier II - Sciences et techniques
2 : MOAIS (INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble)
INRIA – Université Joseph Fourier - Grenoble I – Institut polytechnique de Grenoble (Grenoble INP) – Université Pierre-Mendès-France - Grenoble II – CNRS : UMR5217
3 : Université Pierre Mendès France (Grenoble 2 UPMF)
Université Pierre-Mendès-France - Grenoble II
4 : Department of Computer Science
CAU Kiel
5 : Institut Universitaire de France (IUF)
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

hal-00738508, version 1
http://hal.archives-ouvertes.fr/hal-00738508
oai:hal.archives-ouvertes.fr:hal-00738508
Contributeur : Marin Bougeret <>
Soumis le : Jeudi 4 Octobre 2012, 14:34:32
Dernière modification le : Jeudi 4 Octobre 2012, 15:47:30

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="hal-00738508"><analytic>
<author><persName><forename>Marin</forename><surname>Bougeret</surname></persName>
<affiliation>
<orgName type="laboratory">LIRMM</orgName>
<orgName type="team">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5506</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Pierre-Francois</forename><surname>Dutot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="team">MOAIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut polytechnique de Grenoble (Grenoble INP)</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">CNRS : UMR5217</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">Grenoble 2 UPMF</orgName>
<orgName type="team">Université Pierre Mendès France</orgName>
<country>FR</country>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
</affiliation>
</author>
<author><persName><forename>Klaus</forename><surname>Jansen</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>DE</country>
<orgName type="institution">CAU Kiel</orgName>
</affiliation>
</author>
<author><persName><forename>Christina</forename><surname>Robenek</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>DE</country>
<orgName type="institution">CAU Kiel</orgName>
</affiliation>
</author>
<author><persName><forename>Denis</forename><surname>Trystram</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="team">MOAIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut polytechnique de Grenoble (Grenoble INP)</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">CNRS : UMR5217</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IUF</orgName>
<orgName type="team">Institut Universitaire de France</orgName>
<country>FR</country>
<orgName type="institution">Ministère de l'Enseignement Supérieur et de la Recherche Scientifique</orgName>
</affiliation>
</author>
<title type="main" level="a">Scheduling jobs on heterogeneous platforms</title></analytic><monogr><title level="m" type="main">COCOON Proceedings</title><meeting>COCOON</meeting><imprint><pubPlace><country>États-Unis</country></pubPlace><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="pp">unkown</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00738508</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00738508/PDF/COCOON2011.pdf</idno></biblStruct>
</listBibl>
</listBibl>