Scheduling with Multiprocessors: A rounding network algorithm with a constant error

The candidate will study some special cases of preemptive open shop problems with multiprocessors. He will in particular concentrate on the situation when the processor set is partitioned into 2 multiprocessors. The two cases of preemptions (at integral times only or at arbitrary times) will be considered and the formulation as a linear programming problem will be exploited to get bounds on the minumum completion time. Interpretations in terms of graph colouring (generaling the edge colouring formulation of the open shop model) will be studied as well. Solvable cases wil be described (obtained by restricting for instance the various types of jobs characterized by their individual operations (on single processors) and their group operations (on multiprocessors)).