Abstract FR:

Plusieurs problèmes d'ordonnancement de type flowshop se modélisent par un produit matriciel dans l'algèbre Max-Plus. L'étude de ce produit permet de redémontrer, unifier et généraliser une majorité de résultats connus sur les problèmes de flowshop à deux machines. L'approche matricielle prend en compte, quelque soit le nombre de machines, des contraintes telles que des temps de montage ou de démontage, des décalages temporels ou des groupements de travaux en sous-lots. De nombreuses bornes, heuristiques ou méthodes, issues de la littérature et souvent construites pour le flowshop sans contrainte, s'adaptent aisément au problèmes matriciel et donc à des flowshops soumis aux contraintes citées prédédemment. Plusieurs bornes sont étudiées en détail. De plus, l'écriture matricielle autorise la prise en compte des contraintes tout en nous dispensant de la manipulation explicite des variables qui les décrivent. En conséquence, la modélisation Max-Plus permet de s'abstraire du détail des calculs et de manipuler des objets mathématiques de plus haut niveau. Les problèmes sont mieux appréhendés, leurs analyses s'effectuent plus simplement et les concepts importants se dégagent naturellement. La minimisation du produit matriciel définit en elle même un problème que l'on peut qualifier de problème d'ordonnancement et qui est un sur-problème du problème d'ordonnancement de type flowshop. Pour le résoudre, une procédure par séparation et évaluation (PSE) est proposée, dont le schéma de séparation, original, s'appuie fortement sur l'associativité du produit matriciel. Cette PSE autorise indifféremment la résolution de problèmes de flowshop avec ou sans contraintes.