Retour au site du LAAS-CNRS

Résumé

Ce travail présente une méthode et des outils pour l'ordonnancement en temps réel d'atelier lorsque des contraintes complexes issues du terrain sont à prendre en compte. L'approche retenue vise à caractériser non pas une solution au problème d'ordonnancement, mais un ensemble de solutions sous la forme de groupes d'opérations permutables. Dans ce contexte, on considère un ensemble d'ordres de fabrication, chacun comportant une date de livraison et une date de début au plus tôt et étant composé d'un ensemble d'opérations d'exécution. Chaque opération d'exécution nécessite simultanément pour sa réalisation un ensemble de ressources cumulatives ou disjonctives, chacune d'elles devant être sélectionnée dans un ensemble prédéfini appelé pool. Les contraintes de précédence entre les opérations d'exécution d'un même ordre de fabrication sont définies par des gammes non linéaires. On propose de caractériser l'activité de préparation nécessaire sur un sous-ensemble des ressources requises pour réaliser une opération d'exécution, par un enchaînement de trois opérations élémentaires de préparation : le démontage, le changement de type et le montage. Chaque activité de préparation dépend de la séquence des opérations d'exécution et chaque opération de préparation peut nécessiter également des ressources complémentaires. Un graphe potentiels-tâches particulier est utilisé pour représenter une séquence de groupes. Basé sur une exploration de ce graphe, un algorithme polynomial d'insertion d'une opération dans un ordonnancement visant à minimiser la conséquence de cette insertion sur les dates de livraison, est défini. Cet algorithme est utilisé dans les méthodes proposées pour générer une séquence de groupes initiale et pour l'amélioration de type tabou de cette séquence. Ces méthodes sont validées sur des problèmes classiques d'ordonnancement de projet et sur des problèmes d'ordonnancement d'atelier avec préparation générés aléatoirement. Un système interactif d'aide à la décision est proposé pour l'ordonnancement en temps réel d'un atelier avec préparation, basé sur l'exploitation de la séquence de groupes. La nouvelle version du logiciel d'ordonnancement en temps réel ORDO basée sur ce travail est déjà installée sur plusieurs sites industriels.

Abstract

This work presents a method and tools for workshop real time scheduling with complex constraints issued from industrial contexts. The proposed approach aims at characterizing a set of solutions for the scheduling problem, instead of a single one, by using groups of permutable operations. A set of manufacturing orders is considered, each of them being characterized by a release date, a due date and a set of processing operations. Each processing operation requires a set of cumulative or disjunctive resources simultaneously, each of them being selected inside a specific resource set called a pool. General precedence constraints between processing operations belonging to the same manufacturing order are defined by non a linear routing. Setup activity which may be necessary on a subset of resources required by a processing operation, is defined as a succession of elementary setup operations: unfixing, reset and fixing operations. Each setup activity depends on the processing operation sequence. A setup operation may require additionally complementary resources. A specific operation-on-node graph is used to represent a group sequence. Based On an exploration of this graph, a polynomial operation insertion algorithm in a given schedule is proposed with insertion consequence minimization as an objective. It is used in the proposed method for initial group sequence generation and in the tabu search procedure defined for improving this initial sequence. Computational experiments are provided on a well-known set of project scheduling benchmarks and on randomly generated workshop scheduling problems with setups. An interactive decision support system is proposed for workshop real time scheduling with setups, based on the generated group sequence. The new release of a shop floor scheduling system called ORDO, which is based on this work, is already used in some industrial companies.

Mots-Clés / Keywords

Ordonnancement; Ressources à capacité limitée; Ressources multiples; Affectation de ressources; Temps de préparation; Conduite temps réel; Aide à la décision; Insertion d¿opérations; Scheduling; Resource constraints; Multi-resource requirements; Resource flexibility; Setup times; Decision support system; Operation insertion; Real-time;