In the framework of the integrated model introduced in Chapter III, we are first interested in finding an optimal schedule in a job-shop. This difficult problem has been largely discussed in the literature for more than 20 years (see [Balas 69], [Mc Mahon et Florian 75], [Baker 87], [Carlier 78], [Lageweg et ai 77], [Barker and Mc Mahon 85] or [Carlier and Pinson 89]), and still remains a major problem in combinatorial optimization. In the general case, it has been shown to be N P-hard (see [Rinnooy Kan 76] for instance).