Prof. D. de Werra,President of IFORS Ecole Polytechnique Fédérale de Lausanne Switzterland
Title
Some combinatorial problems in multiprocessor scheduling
Time
2012.10.17 3:30pm
Venue
S703
Abstract
We shall start from the basic classical open shop model with processors and jobs to be processed on the processors according to some requirements. We shall concentrate on the case in which some processors have to be grouped (becoming so multiprocessors) in order to perform some of the tasks required by the jobs. Such a model which has been studied by some authors is motivated by applications in timetabling as well as in testing of electronic systems in particular. We shall describe these applications and review the basic results related to the simple cases of ordinary open shop. Complexity issues will be discussed for the situations in which some grouping of processors is required to cope with the needs of applications. The presentation is based on joint work with W.Kubiak and T.Kis.