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 .
Complete list of metadatas

https://hal.inria.fr/hal-00798444
Contributor : Grégory Mounié <>
Submitted on : Friday, March 8, 2013 - 3:31:52 PM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM

Identifiers

Collections

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. pp.316-327, ⟨10.1007/978-3-642-15240-5₂3⟩. ⟨hal-00798444⟩

Share

Metrics

Record views

353