  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.
