Approximating the Non-contiguous Multiple Organization Packing Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Approximating the Non-contiguous Multiple Organization Packing Problem

Résumé

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 .
Fichier non déposé

Dates et versions

hal-00798444 , version 1 (08-03-2013)

Identifiants

Citer

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. pp.316-327, ⟨10.1007/978-3-642-15240-5₂3⟩. ⟨hal-00798444⟩
134 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More