Contribution à la résolution du Job shop à 2-machines avec convoyeur.

Abstract

Dans un atelier manufacturier, le job shop à deux machines et un seul convoyeur est étudié. Le moyen de transport ou convoyeur est chargé de transporter les tâches semifinies entre les deux machines. Une tâche est dite semi-finie si elle est exécutée sur une des deux machines et les opérations élémentaires qui la constituent ne sont pas toutes exécutées. Deux zones tampons ou aires de stockage appelées zones de stockage d'entrée et de sortie sont en face de chacune des deux machines. Elles sont supposées de capacité illimitée. Les zones de stockages d'entrée et de sortie et la machine qui est en face constituent une station. Le transport d'une tâche entre deux machines peut être décrit comme son chargement de la zone de stockage de sortie d'une machine sur le convoyeur, du transport entre les deux machines et du déchargement de la tâche dans la zone de stockage d'entrée de la seconde d'exécution de la première tâche jusqu'à la fin d'exécution de la dernière tâche. Il représente la longueur d'ordonnancement appelé makespan et noté Cmax. De la littérature, trois règles de priorité « statiques » sont proposées pour la résolution du problème. Une nouvelle règle de priorité « dynamique » appelée OPBM, Ordonnancement par Priorités Bornées en Moyenne, est définie, modifiée et utilisée. Un algorithme OCF-J2(1)C max, une métaheuristique stochastique de type colonie de fourmis, l'OPBM-étendu, la règle de Jackson sont présentés et implémentés par nos soins en utilisant un langage de programmation évolué. Le temps de CPU appelé aussi temps machine, le rapport relatif moyen et la longueur d'ordonnancement Cmax ont constitué les critères de notre étude comparative. Quel que soit le nombre de tâches à exécuter, la règle de Jackson a fourni un temps CPU le plus court. Sa solution réalisable obtenue n'est pas la meilleure parmi les solutions fournies par les trois méthodes. Pour la fonction Cmax, l'OPBM-étendu, OCF-J2(1)Cmax et la règle de Jackson forment un ordre décroissant de performances. Ces dernières sont confirmées par l'exécution de 5x100 instances de problèmes tests de 10, 50, 100, 200 et 400 tâches. Ces instances sont générées de manière aléatoire d'une distribution uniforme. Mots-clés : job shop, convoyeur, colonie de fourmis, temps de transport, OPBM, règle de jackson