Amotz Bar-Noy

Faculty of Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel.

amotz@eng.tau.ac.il.Magnús M. Halldórsson

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

AND University of BergenGuy Kortsarz

Computer Science Dept., Open University, Ramat Aviv, Israel.

guyk@tavor.openu.ac.ilRavit Salman

Dept. of Mathematics, Technion, Haifa 32000, Israel.

maravit@tx.technion.ac.ilHadas Shachnai

The Department of Computer Science, Technion, Haifa 32000, Israel.

hadas@cs.technion.ac.il

Scheduling dependent jobs on multiple machines is modeled by the graph
*multicoloring* problem. In this paper we consider the problem of
minimizing the average completion time of all jobs. This is formalized
as the * sum multicoloring* problem: Given a graph and the
number of colors required by each vertex, find a multicoloring which
minimizes the sum of the largest colors assigned to the vertices. It
reduces to the known *sum coloring* problem when each vertex
requires exactly one color.
This paper reports a comprehensive study of the sum multicoloring problem,
treating three models: with and without preemptions, as well as
co-scheduling where jobs cannot start while others are running. We establish
a linear relation between the approximability of the maximum independent set
problem and the approximability of the sum multicoloring problem in all
three models, via a link to the sum coloring problem. Thus, for classes of
graphs for which the independent set problem is r-approximable, we
obtain O(r)-approximations for preemptive and co-scheduling sum
multicoloring, and O(r log n)-approximation for nonpreemptive
sum multicoloring. In addition, we give constant ratio approximations
for a number of fundamental classes of graphs, including bipartite, line,
bounded degree, and planar graphs.

Submitted, July 3, 1999.