Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux

Type de document

RAPPORT DE RECHERCHE

Langue

francais

Auteur

BENASSER ; YIM

Résumé / Abstract

On veut établir des parcours des trains. Le problème se ramène à un problème d'affectation et d'ordonnancement dans un système de production : une tâche est un parcours d'un canton, les ressources sont les cantons et les pièces sont les trains. Ce problème d'ordonnancement possède les caractéristiques suivantes : - les tâches peuvent nécessiter plusieurs ressources ; - après la fin d'une tâche, les ressources utilisées ne sont pas rendues tant que la tâche suivante n'a pas débuté ; - les 'gammes opératoires' sont flexibles : un travail peut être réalisé de plusieurs manières. Le fait que les ressources ne soient rendues disponibles qu'après le début de la tâche suivante peut amener le système à se bloquer : en effet on peut se retrouver dans une configuration ou les pièces utilisent des ressources et attendent mutuellement d'autres ressources avant de libérer celles qu'elles occupent. Ce problème se rapproche du job-shop multi-ressources avec blocages (job-shop MRB) défini par Berenice Damasceno et Xiao-Lan Xie. Dans ces travaux, les gammes opératoires étaient linéaires. Chaque travail suivait une suite prédéfinie de tâches et ainsi, le problème consistait à établir pour chaque ressource partagée l'ordre d'exécution des tâches (problème d'ordonnancement). Ici, les gammes sont flexibles : un train peut emprunter plusieurs parcours. En plus de l'ordonnancement, il est nécessaire au préalable d'affecter les ressources aux différentes tâches, c'est-à-dire de définir les cantons que suivront les trains. Nous proposons ici une approche basée sur les réseaux de Pétri. Nous verrons que le problème d'ordonnancement se ramène à une recherche de séquences de tir dans un réseau de Pétri entre deux marquages. Cette recherche de séquences de tir s'effectue en utilisant les concepts de marquage partiel et de step partiel. Une campagne d'essais est en cours de réalisations. Actuellement, l'approche proposée est basée sur une technique d'analyse des réseaux de Pétri fondée sur l'abstraction logique. Elle consiste à rechercher les plus petites séquences de steps. Ceci revient à maximiser le parallélisme. Il est possible d'optimiser d'autres critères comme par exemple minimiser les retards. Dans ce cas, il est nécessaire d'utiliser les réseaux de Pétri de haut niveau. L'outil design-CPN est bien adapté à ce type de problème. Il est en effet possible de distinguer les jetons du réseaux : chaque train peut ainsi être individualisé. Par ailleurs, les jetons peuvent contenir des attributs tels que la vitesse ou la longueur. Une autre solution consiste à utiliser l'abstraction logique dans les réseaux de Pétri de haut niveau. L'abstraction logique qui a été présentée dans ce rapport ne concerne que les réseaux de Pétri ordinaires. L'adaptation aux réseaux de haut niveau ne pose pas de difficultés majeures. (étude encadrée par J. Rodriguez - resp. Inrets-ESTAS)., RAPPORT DE CONTRAT