Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A FPTAS for scheduling with memory constraints on graphs with bounded tree-width

Abstract : In this paper we study the scheduling problem under memory constraints, noted P k|G, mem|C$_{max}$, that arise from executing numerical simulations on HPC architectures. We assume that the tree-width of the graph G is bounded by a constant, and we present a fully polynomial time approximation scheme (FPTAS) based on a dynamic programming algorithm. It allows to find a solution within a factor of $1 + \epsilon$ of the optimal makespan, where the capacity of the machines may be exceeded by a factor at most $1 + \epsilon$. This result extends somehow a previous fixed-parameter tractable algorithm with respect to the path-width of the graph G, and rely on the use of a nice tree decomposition of G and its traversal in a specific way which may be useful on its own. The case of unrelated machines, i.e. Rk|G, mem|C$_{max}$, is also tractable with minor modifications.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Sébastien Morais Connect in order to contact the contributor
Submitted on : Friday, June 18, 2021 - 11:33:52 AM
Last modification on : Monday, December 13, 2021 - 9:17:30 AM
Long-term archiving on: : Sunday, September 19, 2021 - 6:26:54 PM


Files produced by the author(s)


  • HAL Id : cea-03264475, version 1


Eric Angel, Sébastien Morais, Damien Regnault. A FPTAS for scheduling with memory constraints on graphs with bounded tree-width. 2021. ⟨cea-03264475⟩



Record views


Files downloads