, SP

C. , =. Min, and C. , sous les contraintes suivantes : C.,: S1.1i* r , S.;i + Pjx S Sit*t, Vl < k < \, ln = 0, Vl <k <\ V Sir

S. +p,

=. Ir, ,. .. , S. , <. , and <. S1, , p.1

, Nous introduisons également I'indicateur suivant : (3.22) (3.23) (3.24) (3.2s)

, Au lieu de résoudre directement le problème (SP). nous considérons la famille de problèmes de décision suivante

, P

, J. jol

, si P(k.r) a une solurion, F(k. t) = I | 0, sinon

, t) vérifie I'existence d'un ordonnancement sans blocage pour les k premières opérations. tel que I'opération (i, k+l) puisse corrmencer au début de la période t. Relation entre les problèmes de décision et le problème à un travail Avant d'aborder la résolution des problèmes de décision, nous montrons que les solutions des problèmes de décision

.. .. Théorème3, . Fnj, and . L}-preuve, Soit t': Min {t / FQ{, t):1}. Nous remarquons que chaque solution {Sir} du problème PG'{.i, t') est un ordonnancement admissible du problème (SP) Donc

C. , toute solution optimale {Sir} du problème (SP) est une solution du problème P(l, Ci) avec C, = S,x1* 1. Alors, F(Nj, C;): L D'ou, C; > t'et

C. and =. , QED Considérons I'ordonnancement suivant : S,u :max {t/F(k-l, t) = I nts Sl

, J r\ ?r -l

S. and *. Sir, 10 : { sl* } est une solution du problème (SP) De plus, Théorème 3 Nj, pour toute solution admissible du problème (SP) avec S1.p1 * r : C

, Preuve : Nous montrons d'abord par induction que S,. existe. Il est clair que S,.N,-r existe

S. Supposons-que, *. *. Alorsr, S. , and *. , 1, c'est-à-dire le problème P(k, S,.u-,) a une solution Soit {S1;. Vl < I < k+l} cene solution Nous avons : S'; -Pjr et F(k, S.;r) = l, ce qui prouve I'existence de S,* . Par induction, tous les Sl* existent. Pour prouver I'admissibilité de {Si* }, il faut vérifier les contraintes de précédence, les contraintes de capacité des ressources et I'absence de blocage. Les contraintes de précédence sont vraies puisque S1r s S,r-, -pjk,Vl s k s \. Les contraintes de capacité sont aussi respectées si lr-,: 0, Vl s k < \

*. S. Srr, De (3.26)Puisque {Srr} est une solution de P(k. S,.*.,), Ik, = 0, v S.;r < r V.3.1 Problème relaxé L'idée est de relaxer les contraintes de capacité des ressources en machines et en AGV en introduisant les multiplicateurs de Lagrange positifs )

U. Multiplicateur and À. , respectivement p) peut être interprété comme le coût de I'utilisation de la machine m (respectivement d'un AGV

. Le-problème-relaxé-peut-Être-mis-sous-la-forme, * ,à^-{È t, S,u <t < s,* + e j-)ôT -l} *?F, h t

, tel que 0i + F*.h' sera dans la partie admissible, c'est à dire que I'inégalité sera vérifrée : L(0

, avec h;: aV;L. la direction du sous-gradient ajustée. D'oir, I'algorithme d'Armijo (Polak , 9l )

. Algorithme-d-', Armijo Paramètres : a, p e (0.1), k' e, Zet

, Etapel, p.0

, Calculer la direction de recherche h1 = crV;L1(x1) Etape 3 : Calculer le pas gi gui vérifie, Etape, vol.2

, ,) ) ag* llvi-1e

, Faire Oi-r = 0i + 9* hi. remplacer ipar i+l et retourner à l'étape l, Etape, vol.4

, Le premier esr que notre position est encore loin de I'optimum alors que le pas de déplacement est faible Le deuxième est le problème d'oscillation de la solution entre deux valeurs. Pour remédier à ces problèmes, d'une part nous fixons un nombre d'itérations au bout desquelles si nous n'arrivons pas à améliorer notre solution, nous faisons décroître le nombre k et donc. nous augmentons le pas de déplacement du facteur lip ; d'autre part. nous cherchons. chaque fois qu'il est possible, à avoir le pas de déplacement le plus grand possible, Il 1 a deux problèmes qui apparaissent parfois avec cette méthode Rappelons que nous sommes en train de chercher un pas cr tel que: 0ln*" = el

, 97) : P. fuchard Contribution des réseaux de Petri à l'étude de problèmes de recherche opérationnelle, Thèse de Doclorat de I'Université de

(. Kan, Complexity and Computations, vol.76

D. W. Rippin, Batch Process Systems Engineering: A Retrospective and Prospective Review, Computers Chim Engr, vol.17, p.13

G. V. Sahinidis, E. Sahinidis, and . Grossmann, Reformulation of multiperiod MILP models for planning and scheduling of chemical processes, Computers & Chemical Engineering, vol.15, issue.4, pp.255-272
DOI : 10.1016/0098-1354(91)85012-J

-. M. Saviv and . Savi, Conception préluninaire des systèmes de production à I'aide des réseaux de Petri: -évaluation des performances, Thèse de Doctorat de I'Université de

T. Sawik, Modelling and scheduling of a Flexible Manufacruring System, European Journal of Operarional Research, vol.45, pp.77-190

B. Schrage, K. R. Schrage, and . Baker, Dynamic programmrrg solution of sequencing problems with precedence constraints, Operations Research, vol.78, issue.26, pp.444-449

. Sethi, Sequencing of Pans and Robot Moves in a Robotic Cell, International Journal of Flexible Manufacturing S1,stems, pp.33-358

G. Nunle, IIE Transactions, vol.20, issue.2, pp.5-7

, Sifakis.78) :J SifakisUse of Petri Nets for Performance Evaluation, Acta Cy,bernel. vol, vol.4, issue.2, pp.185-202

, J Sifakis "Performance Evaluation of Systems using Petri Nets", Net Theory' and Application. Lecture ,\'otes in Contputer Science

P. Slot and . Van-vliet, Analyical Model for FMS Design Optrmization : A Survev, Iàe lnternational Journal of Flexible Manufacturing .!i,slens, issue.6, pp.209-233

. Soriano, P. Gendreau, . Soriano, and . Gendreau, Fondements et applications des m??thodes de recherche avec tabous, RAIRO - Operations Research, vol.31, issue.2, pp.133-159
DOI : 10.1111/j.1937-5956.1992.tb00341.x

K. E. Steck, Design, PIannrng. Scheduling, and Connol hoblems of Flexible ManufacrurLng S),stems, Annals of Operations Research, vol.853, pp.3-12

T. Tomastik, Scheduling flexible manufacturing systems for apparel production, IEEE Transactions on Robotics and Automation, vol.12, issue.5, pp.189-799
DOI : 10.1109/70.538983

V. Larhoven, 92): PJob-Shop Scheduline bv Simulated Annealing, Operations Research, vol.40, issue.l, pp.3-125

. Vignier, Les problèmes de flow-shop hybrides : étar de I'art". RAIRO-RO sous presse, 1997.

. Bibliographie and . Viswanaradham, 90) : N ViswanaradhamDeadlock prevention and Petri net Models, Narahari, Deadlock Avoidance in Flexible Manufacturing Systems Using Robotics and .AulomationGestion Hiérarchisée de Systèmes de hoduction Discrets: Une Approche Basée sur les Réseaux de Petri Thèse de Doctorat de I'Université de

, Modular modeling usrng Petri nets, IEEE Transactions on Robotics, vol.4, issue.12, pp.800-809

X. Xie and . Xie, Connôle Hierarchique d'un Système de Production soumis à Pernrrbations, Thèse de Doctorat de I'Université de

, -s) : X Xie "Analy'se. Conception et Connôle des Systèmes de hoduction, Habilirarion à Diriser des Recherches en Sciences

K. B. Xrng, . H. Hu, and . Chen, DeadlockAvoidancePolicy,forPeni NerModelingof Flexible Manufacrurin-g Srstems u'ith Shared Resources, IEEE Transactions on Automatic and Control, vol.at, issue.96 2, pp.289-295

Z. Xiong, . M. Xiong, and . Zhou, scheduling of Semiconducror resr faciliry Perri ners and Hybrid Heuristic Search, IEEE Transaclions on semiconduclor Manufacturirzg, vol.98, issue.3, pp.38-393

L. Zuberek and . Soutenue, Applicarion of timed manufacruring cells". Technical Repon 49503. Department Foundland. Sr John's. NF. Canada Pefri nets to modeling and anall

. Titre-de-la-thèse, << Ordonnancement des s1'stèmes de production multiressources avec la prise en compte de blocages

, Date de soutenance : le 4 mars 1, p.999

N. N{, D. Baptiste, G. Dauzere-peres, I. Per-e, and . De-oliveira, c,ct>T- N{embres du jurr

, I7t I ll7 7 îf -fÊfi ES 4,/i-r, 1' ,^' de Thèse Résumé L'automatisation des systèmes de production conduit à I'utilisation d'une grande variété de ressources de fabrication ; un aspect longlemps négligé dans la planification et I'ordonnancement de production et qui pose un problème de coordination de I'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 Multi-Ressoruces 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 à I'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 I'opération suivante, thèse ne pouvant être reproduite ! thèse pouvant être reproduite après corrections suggérées au cours de la soutenance Le Président du Jury Corrections effecruées le 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 anestenl I'efficacité des méthodes proposées

. Ordonnancement, S1'stèmes de Production. Opérations à Ressources Multiples