Ordonnancement des systèmes de production multi-ressources avec la prise en compte de blocage
Abstract
This work is motived by the extensive use of a wide range of manufacturing resources in today's production systems. We propose an integrated approach of deadlock avoidance of such systems. For this purpose, we propose a scheduling model, called job-shop with Multiple Resources and Blocking. In this model, an operation may need more than one resource and it is called Multi-Resources operation. Further, upon the completion of an operation of the same job cannot be released and the remaining resources are released at the beginning of the next operation. The later characteristic is called ?hold while waiting? property. The scheduling problem consists in sequency the operations such that deadlocks are avoided and the total duration,i.e. makespan, is minimized. We prove that the problem is strongly NP-Hard. This leads us to propose efficient heuristic methods to construct deadlock-free schedules. Finally, we consider a class of job-shops with Multiple Resources and Blocking : the job-shops with AGV. A Lagrangien Relaxation approach is proposed to solve the scheduling problem. Numerical results are given to show the efficiency the proposed methods
L'automatisation des systèmes de production conduit à l'utilisation d'une grande variété de ressources de fabrication ; un aspect longtemps négligé dans la planification et l'ordonnancement de production et qui pose un problème de coordination de l'ensemble de ressources. Dans ce travail, nous proposons une approche intégrée d'ordonnancement qui prend en compte simultanément cette variété de ressources et le problème de blocage. Pour cela, nous proposons un modèle d'ordonnancement, appelé job-shop Multiple-Ressources avec Blocage ou job-shop MRB. Les deux caractéristiques saillantes du modèle que nous proposons sont : (i) les opérations nécessitant simultanément des ressources de différents types que nous appelons opérations à ressources multiples ; (ii) la contrainte retenir et attendre pour le passage d'une opération à l'opération suivante du même travail, c'est-à-dire que les ressources nécessaires pour une opération ne sont libérées qu'au début de l'opération suivante. Nous montrons que le problème est fortement combinatoire. Pour cela, nous proposons des méthodes heuristiques, utilisant les réseaux de Petri pour la détection de blocage et la programmation dynamique, pour construire des ordonnancements sans blocage efficaces dans un temps raisonnable. enfin, nous considérons un cas particulier : les job-shops avec moyens de transport et proposons une méthode de relaxation Lagrangienne pour construire des ordonnancements efficaces. Les résultats numériques obtenus attestent l'efficacité des méthodes proposées
Domains
Engineering Sciences [physics]Origin | Files produced by the author(s) |
---|
Loading...