Skip to Main content Skip to Navigation
Conference 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 :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03762328
Contributor : Frédéric Davesne Connect in order to contact the contributor
Submitted on : Saturday, August 27, 2022 - 10:24:41 AM
Last modification on : Friday, September 2, 2022 - 10:09:23 AM

Identifiers

Citation

Eric Angel, Sébastien Morais, Damien Regnault. A Bi-criteria FPTAS for scheduling with memory constraints on graphs with bounded tree-width. 28th International Conference on Parallel and Distributed Computing(Euro-Par 2022), Aug 2022, Glasgow, United Kingdom. pp.136--151, ⟨10.1007/978-3-031-12597-3_9⟩. ⟨hal-03762328⟩

Share

Metrics

Record views

12