Des problèmes polynomiaux: Problème d’ordonnancement d’atelier

Abstract

Une classe de problèmes d’analyse combinatoire est considéré, c’est la classe des problèmes d’ordonnancement d’atelier: que se soit ceux a ressource unique ou a multiple ressources. Une étude globale à été faite pour quelques problèmes polynomiaux avec leurs méthodes de solution. Aussi une étude comparative numérique entre deux heuristiques à été établit pour la résolution approchée du problème NP-difficile 1 ‖ ∑▒w_i T_i. Ceux sont en fait les règles SWPT; EDD, solutions optimales respectivement de 1 ‖ ∑▒w_i C_i / 1 ‖ ∑▒L_max qui sont utilisées comme heuristiques pour déterminer une solution approchée pour le problème considéré. Une comparaison numérique à été faite à la fin de ce manuscrit, l’algorithme général à été programmé en utilisant Java.