Bornes inférieures et méthodes exactes pour des problèmes d'ordonnancement disjonctifs

Les problèmes d'ordonnancement disjonctifs consistent à ordonnancer un ensemble de tâches sur une ou plusieurs machines de manière à optimiser certains critères.Nous avons travaillé sur deux types de problèmes NP-difficiles au sens fort. Le premier est la minimisation du retard pondéré sur machine unique. Alors que les meilleurs résultats obtenus sur ce type de problèmes étaient liés à l'utilisation de bornes inférieures linéaires rapides à calculer, mais de qualité parfois médiocre, nous avons envisagé de trouver un compromis entre une borne de qualité et robuste, mais plus coûteuse en temps de calcul, et une énumération intensive des solutions. Cette borne nous est donnée par une technique de décomposition lagrangienne sur un programme linéaire en 0-1 indexé sur le temps. Elle a un écart avec l'optimum inférieur à 1 % sur des instances à 40 et 50 tâches, et elle est sensible à la réduction du domaine des tâches. Elle permet aussi l'élaboration d'une heuristique lagrangienne très efficace (écart de 0,03% avec l'optimum). Incluses dans un branch and bound, ces bornes permettent pour la première fois la résolution des 250 instances proposées par Crauwe1s et al. Nous détaillons également une approche similaire permettant la résolution d'instances ayant jusqu'à 100 tâches. Le deuxième problème est la minimisation du nombre pondéré de tâches en retard sur machines parallèles. Nous proposons ici deux bornes inférieures, l'une basée sur une technique de relaxation lagrangienne, l'autre sur une technique de décomposition lagrangienne. Là encore, les bornes sont de qualité et dans le cas de la décomposition, l'heuristique lagrangienne mise en œuvre est également très performante, notamment lorsque les poids sont tous unitaires. Incluses dans un branch and bound, ces bornes donnent de très bons résultats, notamment avec la décomposition qui permet de résoudre 87,2% des instances à 50 tâches proposées par Baptiste et al.COMPIEGNE-BU (601592101) / SudocSudocFranceF