Given a graph G = (V, E), we consider the problem of finding a set of
D pairwise disjoint cliques in the graph with maximum overall number o
f vertices. We determine the computational complexity of this problem
restricted to a variety of different graph classes. We give polynomial
time algorithms for the problem restricted to interval graphs, cograf
ts, directed path graphs and partial k-trees. In contrast, we show ril
e NP-completeness of this problem for undirected path graphs. Moreover
, we investigate a closely related scheduling problem. Given D times u
nits, we look for a sequence of workers w(1),...,w(k) and a partition
J(1),...,J(k) of the job set such that J(i) can be executed by w(i) wi
thin D time limits. The goal is to find a sequence with minimum total
wage of the workers.