Scheduling dependent jobs on multiple machines is modeled by the graph mult
icoloring problem. In this paper we consider the problem of minimizing the
average completion time of all jobs. This is formalized as the sum multicol
oring problem: Given a graph and the number of colors required by each vert
ex, find a multicoloring which minimizes the sum of the largest colors assi
gned to the vertices. It reduces to the known sum coloring problem when eac
h 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-scheduli
ng 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 mode
ls, via a link to the sum coloring problem. Thus, for classes of graphs for
which the independent set problem is rho -approximable, we obtain O(rho)-a
pproximations for preemptive and co-scheduling sum multicoloring and O(rho
log n)-approximation for nonpreemptive sum multicoloring. In addition, we g
ive constant ratio approximations for a number of fundamental classes of gr
aphs, including bipartite, line, bounded degree, and planar graphs. (C) 200
0 Academic Press.