A FPTAS for scheduling with memory constraints on graphs with bounded tree-width - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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

(1) , (2, 3) , (1)
1
2
3

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.
Fichier principal
Vignette du fichier
FPTAS_SMC_Bounded_TW.pdf (346.91 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

cea-03264475 , version 1 (18-06-2021)

Identifiers

  • HAL Id : cea-03264475 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More