Résultats de complexité et programmation par contraintes pour l'ordonnancement

Baker [9] defines scheduling as the problem of allocating scarce resources to activities over time1. Inthis manuscript, we consider several scheduling problems with a variety of different environments.The two parts of this manuscript provide an overview of two of our major research interests. The firstpart (Chapters 2 to 5) is dedicated to polynomial time solutions of equal{processing{time schedulingproblems. The second one (Chapters 7 to 15) deals with the application of Constraint Programmingto scheduling. These two parts reect the balance we have tried to keep between theoretical andmore applied research.Although all the topics covered in this manuscript are related to scheduling, Parts 1 and 2 arededicated to very different aspects of scheduling. Some few results discussed in Part 1 are occasionallyused in Part 2 but they are independent one from another. In the following, we briey review thecontent Parts 1 and 2. More detailed introductions are provided in Sections 1 and 7 respectively