Approximating the Non-contiguous Multiple Organization Packing Problem

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(npmax)), where pmax 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
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.316-327, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_23〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054450
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:53
Dernière modification le : mercredi 18 juillet 2018 - 11:52:05
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:57:42

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Marin Bougeret, Pierre François Dutot, Klaus Jansen, Christina Otte, Denis Trystram. Approximating the Non-contiguous Multiple Organization Packing Problem. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.316-327, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_23〉. 〈hal-01054450〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

150