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 .
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01054450
Contributor : Hal Ifip <>
Submitted on : Wednesday, August 6, 2014 - 4:24:53 PM
Last modification on : Friday, May 3, 2019 - 12:08:01 PM
Long-term archiving on : Wednesday, November 26, 2014 - 12:57:42 AM

File

03230316.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Marin Bougeret, Pierre François Dutot, Klaus Jansen, Christina Otte, Denis Trystram. Approximating the Non-contiguous Multiple Organization Packing Problem. 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. pp.316-327, ⟨10.1007/978-3-642-15240-5_23⟩. ⟨hal-01054450⟩

Share

Metrics

Record views

169

Files downloads

440