Multi-coloring planar graphs and partial k-trees

At each round we may choose a set of jobs (and process a unit of each of the selected jobs),
such that no two chosen jobs use the same resource.

This problem is modeled by a ``conflict graph'' as follows:
the vertices are the jobs, and two ``conflicting'' jobs are joined by an edge.
The color requirment $x(v)$ of a job $v$ represents the length of job $v$
(that is, the number of units it takes to complete the job).
A solution assignes $x(v)$ colors (positive integers) to each vertex $v$
representing the time units where $v$ is being processed.
Let $f(v)$ be the maximum integer assigned to $v$ (that is, $f(v)$ is the time job $v$ is finished).

The usual optimization goal is to minimize $\max_v {f(v)}$,
that is, to minimize the number of colors used by the multi-coloring.
Another optimization goal is to minimize the average finish time of all jobs.

We present new approximation schemes for the cases
(i) the conflict graph is planar, and
(ii) the conflict graph has tree-width bounded by $k$.