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

A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-width

Abstract : In this paper we study a scheduling problem arising from executing numerical simulations on HPC architectures. With a constant number of parallel machines, the objective is to minimize the makespan under memory constraints for the machines. Those constraints come from a neighborhood graph G for the jobs. Motivated by a previous result on graphs G with bounded path-width, our focus is on the case when the neighborhood graph G has bounded tree-width. Our result is a bi-criteria fully polynomial time approximation algorithm based on a dynamic programming algorithm. It allows to find a solution within a factor of 1 +  of the optimal makespan, where the memory capacity of the machines may be exceeded by a factor at most 1 + . This result relies 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 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 : Thursday, February 17, 2022 - 4:30:23 PM
Last modification on : Saturday, March 26, 2022 - 4:08:12 AM
Long-term archiving on: : Wednesday, May 18, 2022 - 7:17:31 PM


Files produced by the author(s)


  • HAL Id : cea-03578940, version 1


Eric Angel, Sébastien Morais, Damien Regnault. A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-width. 2022. ⟨cea-03578940⟩



Record views


Files downloads