Approximating the Non-contiguous Multiple Organization Packing Problem

Marin Bougeret 1 Pierre-François Dutot 1 Klaus Jansen 2 Christina Otte 2 Denis Trystram 1
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 Theory of Parallelism
Department of Computer Science
Abstract : We present in this paper a -approximation algorithm for scheduling rigid jobs on multi-organizations. For a given set of n jobs, the goal is to construct a schedule for N organizations (composed each of m identical processors) minimizing the maximum completion time (makespan). This algorithm runs in O(n(N + log(n))log(np max )), where p max is the maximum processing time of the jobs. It improves the best existing low cost approximation algorithms. Moreover, the proposed analysis can be extended to a more generic approach which suggests different job partitions that could lead to low cost approximation algorithms of ratio better than .
Type de document :
Communication dans un congrès
TCS: Theoretical Computer Science, 2010, Brisbane, Australia. 6th International Conference on Theoretical Computer Science, 323, pp.316-327, 2010, IFIP Advances in Information and Communication Technology. 〈10.1007/978-3-642-15240-5₂3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00798444
Contributeur : Grégory Mounié <>
Soumis le : vendredi 8 mars 2013 - 15:31:52
Dernière modification le : mercredi 11 avril 2018 - 01:56:26

Identifiants

Citation

Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Otte, Denis Trystram. Approximating the Non-contiguous Multiple Organization Packing Problem. TCS: Theoretical Computer Science, 2010, Brisbane, Australia. 6th International Conference on Theoretical Computer Science, 323, pp.316-327, 2010, IFIP Advances in Information and Communication Technology. 〈10.1007/978-3-642-15240-5₂3〉. 〈hal-00798444〉

Partager

Métriques

Consultations de la notice

295