Le problème étudié est un modèle de flowshop avec contraintes de délai, minimal et maximal, entre les opérations d'une même tâche, au sein duquel deux critères sont optimisés hiérarchiquement, en premier lieu le nombre de tâches en retard et en second lieu le makespan. Une étude antérieure s'est intéressée au cas particulier du flowshop de permutation (voir E. Dhouib et al., chapitre 4 In Eds B. Jarboui, P.Siarry et J. Teghem, «Métaheuristiques pour l'ordonnancement monocritère des ateliers de production », Hermès-Lavoisier,2013).

Nous traitons ici du cas général d'un tel flowshop mais avec deux machines, pour lequel les contraintes de délai font que les permutations ne forment plus généralement un ensemble dominant. Outre une modélisation MILP, l'objet du travail vise à analyser, en partant de la meilleure permutation, s'il est possible d'améliorer les performances en transposant deux jobs successifs sur une seule machine. Une étude théorique met en évidence

- d'abord des conditions pour qu'une telle transposition fournisse une solution admissible ;

- ensuite des conditions pour qu'une telle transposition soit intéressante du point de vue de l'optimisation hiérarchique.

Cette étude dégage une nouvelle propriété de dominance des permutations.

Basée sur cette étude théorique, une heuristique est proposée pour construire une solution de non-permutation meilleure. Des expérimentations numériques sont réalisées pour illustrer l'étude.