A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-width - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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

Dates and versions

cea-03578940 , version 1 (17-02-2022)

Identifiers

  • HAL Id : cea-03578940 , version 1

Cite

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⟩
10 View
17 Download

Share

Gmail Facebook Twitter LinkedIn More