de Werra

Some coloring models for chromatic scheduling

Vortrag von Prof. Dr. Dominique de Werra
(Ecole Polytechnique Fédérale de Lausanne)


Graph coloring models are often unable to provide an efficient help in the solution of real timetabling or scheduling problems; the reason is that there are many additional requirements which have to be introduced. In this talk we will consider some of these and in particular the existence of feasible sets of colors. These "local" requirements will be combined with "global" constraints (like bounds on the cardinalities of the color glasses) and we discuss complexity of this problem. Applications in timetabling as well as in robotics will be given.