  In scheduling and timetabling applications, the mutual-exclusion constraint
stipulates that certain pairs of tasks that cannot be executed at the same
time. This corresponds to the vertex colouring problem in graph theory, for
which there are well-known semidefinite programming (SDP) relaxations. In
practice, however, the mutual-exclusion constraint is typically combined with
many other constraints, whose SDP representability has not been studied.
  We present SDP relaxations for a variety of mutual-exclusion scheduling and
timetabling problems, starting from a bound on the number of tasks executed
within each period, which corresponds to graph colouring bounded in the number
of uses of each colour. In theory, this provides the strongest known bounds for
these problems that are computable to any precision in time polynomial in the
dimensions. In practice, we report encouraging computational results on random
graphs, Knesser graphs, ``forbidden intersection'' graphs, the Toronto
benchmark, and the International Timetabling Competition.
