A batch is a set of jobs that start execution at the same time; only when the last job is completed can the next batch be started. When there are constraints or conflicts between the jobs, we need to ensure that jobs in the same batch be non-conflicting. That is, we seek a coloring of the conflict graph. The two most common objectives of schedules and colorings are the makespan, or the maximum job completion time, and the sum of job completion times. This gives rise to two types of  batch coloring problems :  max-coloring and  batch sum coloring , respectively.#R##N##R##N#We give the first  polynomial time approximation schemes for batch sum coloring on several classes of "non-thick" graphs that arise in applications. This includes paths, trees, partial  k -trees, and planar graphs. Also, we give an improved  O ( n  log  n ) exact algorithm for the max-coloring problem on paths.
['Magnús M. Halldórsson', 'Hadas Shachnai']
Batch Coloring Flat Graphs and Thin