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

Eric Angel (1) , Sébastien Morais (2, 3) , Damien Regnault (1)

1 IBISC - Informatique, BioInformatique, Systèmes Complexes
2 CEA, Bruyeres le Chatel, France
3 LIHPC - Laboratoire en Informatique Haute Performance pour le Calcul et la simulation

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.

Domaines: Informatique [cs]

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