Restrictions of Graph Partition Problems
Hans L. Bodlaender, Klaus Jansen · 1993
Let J be a set of n jobs, all with job processing time or job length one, and let M be a set of k machines. Incompatibilities between jobs are described by an undirected graph G = (J, E) with vertex set J. If G contains an edge between two jobs j and j′ (j ≠ j′), we demand that these two jobs can not be executed by the same machine. An assignment of the jobs to the machines, which satisfies the incompatibility relation, is called a schedule. The processing time of a machine is given by the number of assigned jobs, since each job has processing time one.