Étude d'un problème d'ordonnancement à une machine avec fenêtre d'exécution et poids associés à certains travaux.

Abstract

La recherche de solution optimale pour le problème d'ordonnancement à une machine avec fenêtres d'exécutions est fortement combinatoire. C'est en particulier le cas lorsque le critère envisagé est la minimisation du nombre de travaux en retard. Dans ce mémoire, et à partir de certains travaux déja réalisés sur l'exploitation de la condition de dominance pour la résolution d'un problème d'optimisation 1|ri| Ui sous forme de PLNE que nous avons exploité, nous avons introduit le problème étudié et rappelé la condition de dominance utilisée pour sa résolution. Nous savons que cette condition donnée par le théorème des pyramides est dominante vis-à-vis de l'admissibilité mais ne l'est pas vis-à-vis de la minimisation du nombre de travaux en retard. Toutefois, il est possible de l'exploiter pour la résolution de notre problème en déterminant des bornes à travers des modèles PLNE adaptés de celui donné pour la détermination de la solution la plus dominantes. Ainsi, nous avons présenté les programmes linéaires en nombres entiers permettant de déterminer des bornes au problème de minimisation du nombre de travaux en retards. Un premier modèle PLNE4 permettant de déterminer la solution optimale au problème lorsque les travaux sommets sont tous en avance et constitue ainsi une borne supérieure, et un second modèle PLNE5 qui permet de déterminer une autre borne supérieure, plus efficace en terme de valeur de la solution retournée. Aussi à travers le même modèle PLNE5, une borne inférieure est déterminée lorsque les données du problème sont relâchées. A la base de ces modèles et au vue daméliorer la qualité des solutions ainsi que leur temps dexécution, nous nous sommes proposés de procéder à un changement de variables qui a conduit à une nouvelle formulation des modèles. D'un autre coté, afin de pouvoir étudier la possibilité daméliorer encore plus les bornes, une notion de poids a été introduite et associée aux variables de décisions. Les formulations mathématiques de programmation linéaire en nombres entiers proposées pour le problème 1|ril Ui ont été implémentées sur le solveur ILOG CPLEX 6.3. Pour cela nous avons mis en en place une application sur C++ afin de traiter les données et de les rendre exploitable par le solveur. Une comparaison avec les résultats de l'approche [6] a montré que les résultats des expérimentations sont trés bons, notamment du point de vue du temps d'exécution et de la qualité des bornes inférieures et supérieures. Il démontrent l'intérêt de notre nouvelle formulation et son éfficacité.Dans notre étude menée dans ce mémoire, nous avons proposé de nouveaux modèles de programmations pour la détermination de bornes aux solutions optimales, et nous nous. sommes proposés d'étudier la possibilité d'améliorer la qualité des solutions en associant des poids aux travaux. Nous avons ainsi touché de près à la notion de dominance et aux modèles de programmation linéaire en variables mixtes et à leur résolution à travers un solveur. Les différentes connaissances acquises nous ont été bénéfiques et nous ont inspiré, en plus du travail réalisé, pour mettre des perspectives de recherche à mener dans les travaux futurs. La plus intéressante, consiste de poursuivre l'étude sur l'intérêt d'associer des poids aux tâches, vue que l'expérimentation de certaines instances a révélé un temps d'exécution très réduit, et faire une analyse plus approfondie sur la structure pyramidale d'une instance pour statuer sur la nécessité d'associer des poids ou pas au problème considéré.