Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

La densité des échanges commerciaux, ainsi que l'intensification de la concurrence qui a suivi, a conduit les entreprises à rationaliser leurs activités, particulièrement celles nécessitant des activités d'ordonnancement. La théorie de l'ordonnancement est une discipline bien établie de l'optimisation combinatoire. Son champ d'investigation concerne les problèmes d'allocation, dans le temps, d'un ensemble limité de ressources par un ensemble de tâches, afin d'optimiser un ou plusieurs critères donnés. Sa popularité vient du fait qu'une multitude de situations peut être ramenée à cette problématique d'ordonnancement. Cela est dû, en grande partie, à la richesse de l'interprétation que peuvent avoir les termes ressources et tâches. Nous pouvons citer, entre autres, des applications dans l'industrie (réalisation de produits sur des machines), la santé (confection d'horaires), l'informatique (exécution de processus). Dans ce mémoire de maîtrise, nous nous intéressons spécifiquement aux problèmes d'ordonnancement d'ateliers de production. Ainsi, notre étude porte sur l'ordonnancement de n tâches (jobs) sur m ressources (machines) dans un environnement de type job shop. Dans le modèle de job shop, chaque tâche doit passer sur l'ensemble des machines, à chaque fois pendant un temps connu à l'avance, et selon également un ordre donné. Le critère, que nous avons choisi pour évaluer la qualité d'une solution, est celui du makespan (la durée totale d'accomplissement des « tâches). Pour rester proche de la réalité industrielle, notre modèle incorpore un convoyeur chargé de transporter les tâches semi-finies d'une machine à une autre. Ce modèle peut être illustré par l'exemple d'une entreprise d'assemblage d'ordinateurs. Les machines assemblent divers éléments (cartes mères, disques durs, barrettes mémoires, etc) dans un boîtier. Un convoyeur déplace le boîtier entre les différentes machines. Suivant les spécifications de chaque ordinateur, chaque boîtier suit un chemin particulier. En effet, si un client souhaite acheter un boîtier contenant uniquement la carte-mère et l'alimentation, ce boîtier ne passera que sur deux machines. Nous nous sommes restreint au problème de job shop à deux machines et un seul convoyeur. Notons que nous supposons que les deux machines possèdent des espaces de stockage de taille illimitée pour recevoir les travaux semi-finis. Notre but était au départ de trouver un algorithme polynomial pour résoudre ce problème. Or, il s'est avéré que même avec ce modèle restreint et simplifié, le problème est NP-difficile. Pour le résoudre, nous nous sommes alors tournés vers l'approche heuristique. Néanmoins, nous avons pu trouver des cas particuliers où ce problème est résoluble en un temps polynomial. Notre démarche a été d'abord d'introduire brièvement les problèmes de la théorie de l'ordonnancement ainsi que quelques concepts de la NP-complétude, avant d'aborder les différentes approches algorithmiques de résolution des problèmes d'ordonnancement. Dans une seconde étape, la littérature relative à cette problématique a été passée en revue. Ensuite, nous avons décrit plus en détail notre modèle de job shop ainsi que son fonctionnement. Nous avons discuté de l'influence du convoyeur sur la minimisation du critère du makespan. Nous avons également proposé une borne inférieure pour ce même critère. Enfin, nous avons discuté et proposé deux approches de résolution approchée. La première est constructive : trois algorithmes, basés sur des règles de priorité, ont été conçus. Les deux premières règles sont fondées sur l'appariement des travaux et la troisième est la règle bien connue de Jackson que nous avons modifiée ; ces règles ont une complexité temporelle en O(nlogn). La seconde approche de résolution est itérative: l'algorithme de recherche avec tabous a été notre choix. Cette méthode étend à n travaux la méthode classique de résolution graphique à deux travaux. Finalement, nous avons entrepris une étude comparative de l'ensemble des algorithmes de résolution proposés. Les deux approches de résolution ont été simulées par un programme Java sur des instances générées de manière aléatoire à partir d'une distribution uniforme. Ces instances sont de tailles n ? 10, 20, 50 et 200. Les temps d'exécution et de transport sont compris entre 0 et 50 unités de temps. La borne inférieure a été utilisée pour évaluer la qualité des solutions générées par chacune de ces heuristiques. Cette étude a montré que, parmi les algorithmes basés sur les règles de priorité, celui de Jackson donne des solutions de meilleure qualité. L'algorithme de recherche avec tabous donne, en moyenne, de meilleures solutions que les algorithmes basés sur les règles de priorité. Toutefois, les temps de calculs de cette approche sont de loin plus importants que ceux générés par les règles de priorité, surtout lorsque la taille des problèmes devient de plus en plus grande. Nous concluons notre travail par la suggestion de nouvelles pistes à explorer pour des recherches futures.