Job Scheduling Using successive Linear Programming Approximations of a Sparse Model

Abstract : In this paper we tackle the well-known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, i.e., the completion time of the last job, this problem has been shown to be NP-Hard and several heuristics have already been proposed to minimize the execution time. We introduce a novel approach based on successive linear programming (LP) approximations of a sparse model. The idea is to relax an integer linear program and use lp norm-based operators to force the solver to find almost-integer solutions that can be assimilated to an integer solution. We consider the case where jobs are either rigid or moldable. A rigid parallel job is performed with a predefined number of processors while a moldable job can define the number of processors that it is using just before it starts its execution. We compare the scheduling approach with the classic Largest Task First list based algorithm and we show that our approach provides good results for small instances of the problem. The contributions of this paper are both the integration of mathematical methods in the scheduling world and the design of a promising approach which gives good results for scheduling problems with less than a hundred processors.
Liste complète des métadonnées

https://hal.inria.fr/hal-00789217
Contributeur : Lamiel Toch <>
Soumis le : dimanche 17 février 2013 - 11:15:38
Dernière modification le : jeudi 11 janvier 2018 - 06:26:54
Document(s) archivé(s) le : samedi 18 mai 2013 - 02:50:08

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00789217, version 1

Citation

Stéphane Chrétien, Jean-Marc Nicod, Laurent Philippe, Veronika Rehn-Sonigo, Lamiel Toch. Job Scheduling Using successive Linear Programming Approximations of a Sparse Model. EuroPar 2012. 2012. 〈hal-00789217〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

720