Abstract FR:

Motive par de nombreuses situations industrielles, comme la production d'acier, la planification de la maintenance de machines et les situations d'urgence, nous considerons dans cette these un nouveau modele de flow shop. Les durees operatoires dans les machines differentes sont variables : plus on retarde l'execution d'une operation, plus sa duree operatoire est longue. Pour ce modele de flow shop avec durees operatoires variables, les ordonnancements de permutation ne sont pas necessairement optimaux. Les problemes consistant a trouver un ordonnancement optimal et a trouver un ordonnancement de permutation optimal sont tous deux np-difficiles. Meme le probleme restreint, ou l'on recherche un placement optimal une fois la sequence de passage des taches donnee, n'est pas evident. L'objectif de cette these est d'une part d'etudier le probleme restreint pour les criteres reguliers les plus importants, et d'autre part de proposer des heuristiques pour le probleme general a deux machines, qui consiste a trouver une permutation optimale. Correspondant a chacun de ces nouveaux modeles, nous definissions un modele inverse. Apres avoir etabli l'equivalence entre chaque modele et son modele inverse, nous etudions les proprietes des placements optimaux sur les modeles inverses pour un critere regulier donne. Nous montrons qu'il existe toujours un placement optimal dans lequel les operations sont placees au plus tot, a partir du deuxieme processeur, une fois la premiere operation lancee. Cette propriete remarquable pour le modele inverse nous permet de proposer des algorithmes de type glouton pour trouver un placement optimal dans le cas du critere de la duree total et du retard algebrique maximum. De plus, les proprietes du probleme restreint nous fournissent egalement des algorithmes approches efficaces pour le probleme general a deux machines.