Preliminary design of manufacturing systems using petri nets
Conception préliminaire des systèmes de production à l'aide des réseaux de Pétri
Résumé
This work is devoted to use of Petri nets for modeling and evaluating non-cyclic manufacturing systems. To model such a system we define a class of Petri nets called RPES (Petri nets with inputs and outputs transitions). After studying the properties of a subclass of RPES, the RPES without conflict, we show how to decompose a RPES into a set of RPES without conflict and define conditions under which the use of RPES without conflict ensures that the system exhibits desirable qualitative properties. The system evaluation is based on a short-term planning followed by a scheduling. The planning problem consists in finding the number of times each RPES without conflict is activated in each elementary period. We show that this problem can be formulated as a linear or quadratic programming problem according to the criterion to be optimized. Efficient methods are proposed for solving this problem. To solve the scheduling problem we propose two heuristics methods : one is a simulated annealing like algorithm and the other one a branch and bound alogithm. To facilitate the use of these algorithms we integrate them into a software with a graphical interface. Next, several comparative studies are done in each step of the evaluation phase. Finally, we apply our methodology on a set of large size examples and we analyse the results
Cette thèse est consacrée à l'utilisation des réseaux de Pétri pour la modélisation et l'évaluation des systèmes de production non-cycliques. Dans un premier temps, nous introduisons une classe particulière de réseaux de Pétri, les réseaux de Pétri avec transitions d'entrée et de sortie (rpes), lesquels permettant de modéliser un système de production non-cyclique. Après avoir étudié les propriétés d'une sous-classe des rpes, les rpes sans conflit, nous montrons comment décomposer un rpes et un ensemble de rpes sans conflit, et nous mettons en évidence les conditions dans lesquelles l'utilisation de ces rpes sans conflit permettra de garantir les propriétés qualitatives souhaitées pour le système. L'évaluation du système passe par la planification à court terme et l'ordonnancement. Le problème de planification consiste à déterminer le nombre de fois qu'un rpes sans conflit extrait du modèle rpes est activé dans chaque période élémentaire. Nous formulons ce problème comme un problème de programmation linéaire en nombres entiers ou un problème de programmation quadratique suivant le critère d'optimisation adopté, et nous proposons des méthodes de résolution efficaces. Nous abordons ensuite le problème de l'ordonnancement et présentons deux algorithmes heuristiques : le premier est basé sur la méthode du recuit simulé et le second sur la procédure par séparation et évaluation. Afin de faciliter l'utilisation des algorithmes nous les avons intégrés sous la forme d'un logiciel interactif. Par la suite, nous faisons une série d'études comparatives entre les algorithmes utilisés dans chacune des étapes de l'évaluation du modèle. Finalement, nous appliquons la méthodologie développée sur une batterie d'exemples de tailles importantes, et nous discutons les résultats obtenus
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...