2022/02/17 by Éric Angel, Angel, Eric, Sébastien Morais +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Parallel #Scheduling and Optimization Algorithms #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.08704
openalex publication_date 2022/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 + epsilon of the optimal makespan, where the memory capacity of the machines may be exceeded by a factor at most 1 + epsilon. 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.