. Si, (b point (i-1, yd) appadient à un obstacle

. Si, le point (i, yd) a été déià pris comme sommet) : lgnorer ce point

. Si, le point (i-1, j) appartient à un obstacle

. Si, le point (i, j) a déjà été pris comme sommet) : lgnorer ce point et continuer

. Si, le point (i, j+1) appartient à un obstacle

. Si, le point (xd, 1) est atteint sans avoir rencontré d'obstacte)

. Si, (xd, 1) n'a jamais été considéré comme sommet

S. Sinon, le point (xd, i-l) appartient à un obstacte

P. Afentakis, R. A. Millen, and M. M. Et-solomon, Dynamic Layout Strategies for Flexible Manufacturing Systeffis, International Journal of Production Research, vol.28, pp.2-31, 1990.

D. Anciaux, Etude d'agencement spacial dans un atelier de production selon le concept de technologie de groupe, Thèse de doctorat de I'université de, 1990.

R. Azencott, Simulated annealing : parallelization techniques, 1992.

. S. Baker-8, E. G. Coffman, and R. L. Et-rivest, Orthogonal Packings in Two Dimensions, SIAM Journal on Computing, vol.9, issue.4, pp.8-14, 1980.
DOI : 10.1137/0209064

E. Balas and J. B. Etmazzola, Nonlinear 0-l Programming : l. Lineaization Techniques, Mathematical Programming, pp.1-22, 1984.

J. Balakrishnan, . F. Jacobs, and M. A. Venkataramanan, Solutions for the constrained dynamic facility layout problem, European Journal of Operational Research, vol.57, issue.2, pp.280-286, 1992.
DOI : 10.1016/0377-2217(92)90049-F

R. Batta, Note???Comment on ???The Dynamics of Plant Layout???, Management Science, vol.33, issue.8, 1987.
DOI : 10.1287/mnsc.33.8.1065

. Bazaraa, An exact branch-and-bound procedure forthe quadratic assignment problem, Naval Research Logistics Quarterly, vol.26, pp.1109-121, 1979.
DOI : 10.1002/nav.3800260111

M. S. Bazaraa and O. Et-kirna, A branch-and-bound-based heuristic for solving the quadratic assignment problem, Naval Research Logistics Quarterly, vol.3, issue.2, pp.287-304, 1983.
DOI : 10.1007/BFb0120905

M. S. Bazaraa and . M. Et-sherali, Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics Quarterly, vol.213, issue.1, pp.29-41, 1980.
DOI : 10.6028/jres.071B.026

J. O. Berkey and P. Y. Wang, Two-Dimensional Finite Bin-Packing Algorithms, Journal of the Operational Research Society, vol.38, issue.5, pp.423-429, 1987.
DOI : 10.1057/jors.1987.70

R. E. Burkard and T. Et-bonninger, A heuristic for quadratic Boolean program with apptications to quadratic assignment problems, European Journal of Operational Research, pp.374-386, 1983.

V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, vol.21, issue.1, pp.41-51, 1985.
DOI : 10.1007/BF00940812

C. Chu, Cluster analysis in manufacturing cellular formation, Omega, vol.17, issue.3, pp.289-295, 1989.
DOI : 10.1016/0305-0483(89)90034-0

W. Dangelmaier, Algorithmen und Vertahren zur Erstellung i n ne rb etri e bti ch e r Ano rdnu ngspl àne, Habilitatio nssch rift gene h mi gt von des Universitât Stuttgart, Fakultât Fertigungstechnik, Hauptberichter : Prof. Dr--lng. H.-J. Warnecke, 1984.
DOI : 10.1007/978-3-642-82677-1

. M. Deisenroth and J. M. Appel, A computerized plant layout analysis and evaluation technique, Annual AllE Conference, 1972.

R. W. Eglese, Simulated annealing: A tool for operational research, European Journal of Operational Research, vol.46, issue.3, pp.271-281, 1990.
DOI : 10.1016/0377-2217(90)90001-R

. El-shefei, Hospital Layout as a Quadratic Assignment Problem, Journal of the Operational Research Society, vol.28, issue.1, pp.167-197, 1977.
DOI : 10.1057/jors.1977.29

G. Finke, R. E. Burkard, and F. Et-rendl, Quadratic assignement Problem, Working paper, Dept. of Applied Mathematics, 1985.

E. L. Fisher and . Y. Et-nof-s, FADES : Knowtedge-based facility design, Proc. Spring lndustrial Engineering conference, pp.74-82, 1984.

J. W. Gavett and N. V. Et-plyter, The Optimal Assignment of Facilities to Locations by Branch and Bound, Operations Research, vol.14, issue.2, pp.210-232, 1966.
DOI : 10.1287/opre.14.2.210

P. C. Gifmore, Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem, Journal of the Society for Industrial and Applied Mathematics, vol.10, issue.2, pp.305-313, 1962.
DOI : 10.1137/0110022

M. Gondran and M. Et-minoux, Graphes et aAlgorithmes, 1990.

S. B. Hamma and C. Et-bonnemoy, La méthode du recuit simulé: Optimization gtobate dans Rn, APPll, vol.25, pp.477-496, 1991.

T. Hamann, Le problème d'agencement des ressources à l'intérieur des cellules des systèmes de fabrication, Thèse de Doctorat, 1992.

T. Hamann and F. Et-vernadat, The lntra-cell Layout Problem in Automated Manufacturing Systems, CARs & FOF '92 8th lnternational Conference on CAD/CAM, Robotics and Factories of the Future, pp.695-708, 1992.

T. Hamann, J. M. Proth, A. Souilah, F. Vernadat, and X. L. Et-xie, COALA : A Manufacturing Plant Layout Approach'l The Eighth International lFlP WG5.3 Conference "PROLAMAT'92, Man in CIM Systems, 1992.

G. Harhalakis, J. M. Proth, and X. L. Xie, Manufacturing cell design using simulated annealing: An industrial application, Journal of Intelligent Manufacturing, vol.2, issue.2, pp.185-191, 1990.
DOI : 10.1007/BF01572637

URL : http://drum.lib.umd.edu/bitstream/1903/5016/1/TR_90-68.pdf

G. Harhalakis and J. M. Et-proth, Some open problems in the design and use of modern production systems, Applied Stochastic Models and Data Analysis, vol.6, issue.1, pp.33-45, 1991.
DOI : 10.1109/TSE.1980.230492

M. M. Hassan and G. L. Hogg, A review of graph theory application to the facilities layout problem, Omega, vol.15, issue.4, pp.291-300, 1987.
DOI : 10.1016/0305-0483(87)90017-X

M. M. Hassan, G. L. Hogg, and D. R. Smith, SHAPE: A construction algorithm for area placement evaluation, International Journal of Production Research, vol.24, issue.5, pp.1283-1295, 1986.
DOI : 10.1080/00207548608919803

S. Heragu and A. Kusiak, Analysis of expert systems in manufacturing design, IEEE Transactions on Systems, Man, and Cybernetics, vol.17, issue.6, pp.898-912, 1987.
DOI : 10.1109/TSMC.1987.6499302

F. S. Hillier, Quantitative tools for plant layout analysis, Journal of lndustrial Engineering, vol.14, pp.33-40, 1963.

F. S. Hillier and M. M. Et-connors, Quadratic Assignment Problem Algorithms and the Location of Indivisible Facilities, Management Science, vol.13, issue.1, pp.42-57, 1966.
DOI : 10.1287/mnsc.13.1.42

B. K. Kaku, G. L. Et-thompson, and . Baybar-l, A heuristic method for the multi-story layout problem, European Journal of Operational Research, vol.37, issue.3, pp.384-397, 1986.
DOI : 10.1016/0377-2217(88)90202-0

B. Kaufman, An algorithm for the quadratic assignment problem using BenderS' decomposition, European Journal Of Operational Research, vol.2, pp.2-4, 1978.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by Simulated Annealing, Science, vol.220, issue.4598, pp.671-680, 1983.
DOI : 10.1126/science.220.4598.671

URL : http://www.cs.virginia.edu/cs432/documents/sa-1983.pdf

T. C. Koopmans and M. Et-beckman, Assignment Problems and the Location of Economic Activities, Econometrica, vol.25, issue.1, pp.53-76, 1957.
DOI : 10.2307/1907742

P. Kouvelis and A. S. Et-kiran, Single and multiple period layout models for automated manufacturing systems, European Journal of Operational Research, vol.52, issue.3, pp.300-314, 1991.
DOI : 10.1016/0377-2217(91)90165-R

K. Kouvelis and . Gutiérrez, Algorithms for robust single and multiple period layout planning for manufacturing systems, European Journal of Operational Research, vol.63, issue.2, pp.287-303, 1992.
DOI : 10.1016/0377-2217(92)90032-5

A. Kusiak, Artificial Intelligence And Operations Research In Flexible Manufacturing Systems, INFOR: Information Systems and Operational Research, vol.25, issue.1, 1987.
DOI : 10.1080/03155986.1987.11732024

A. Kusiak, lntelligent Manufacturing systems, 1990.

T. A. Lacksonen and E. E. Et-enscore, Quadratic assignment algorithms for the dynamic layout problem, International Journal of Production Research, vol.19, issue.3, pp.503-517, 1993.
DOI : 10.1287/mnsc.12.10.B450

E. L. Lawler, The Quadratic Assignment Problem, Management Science, vol.9, issue.4, pp.586-599, 1963.
DOI : 10.1287/mnsc.9.4.586

R. C. Lee and J. M. Et-moore, RELAP : computerized RElationship layout planning, Dept. of Industrial Engineering, Northeastern University, U.S.A. and the Journal of Industrial Engineering, vol.18, issue.3, pp.195-200, 1967.

B. Malakooti, Computer-aided facility tayout selection (CAFLAS) with apptications to multipte citeria manufacturing planning problems, Large Scale SYstems, vol.1, issue.2, pp.109-123, 1987.

B. Minten, Beitrag zur rechnergestùzten FabikplantJng, Diss. Universitât Stuttgart, issue.1g77

J. Mcauley, Machine grouping for efficient production, Production Engineer, vol.51, issue.2, pp.53-57, 1972.
DOI : 10.1049/tpe.1972.0006

B. Montreuil and U. Et-venkatadri, Strategic Interpolative Design of Dynamic Manufacturing Systems Layouts, Management Science, vol.37, issue.6, pp.682-694, 1991.
DOI : 10.1287/mnsc.37.6.682

B. Montreuif and A. Et-laforge, Dynamic layout design given a scenario tree of probable futures, European Journal of Operational Research, vol.63, issue.2, pp.271-286, 1992.
DOI : 10.1016/0377-2217(92)90031-4

A. Nozari and . E. Et-enscore-jr, Computerized facility layout with graph theory, Computers & Industrial Engineering, vol.5, issue.3, p.183, 0193.
DOI : 10.1016/0360-8352(81)90004-8

C. E. Nugent, T. E. Vollmann, and R. Et-ruml, An Experimental Comparison of Techniques for the Assignment of Facilities to Locations, Operations Research, vol.16, issue.1, pp.150-173, 1968.
DOI : 10.1287/opre.16.1.150

J. M. Proth and A. Souilah, Near-Optimal Layout Algorithm Based on Simulated Annealing, International Journal of Systems Automation : Research and Applications (SARA), vol.2, pp.227-243, 1992.

R. Rajagopalan and J. L. Et-batra, Design of Cellular Production Systems'A Graph Theoretic Approach, lnternational Journal of Production Research, 1975.

J. Rose, W. Klebsch, and J. Et-wolf, Temperature measurement and equilibrium dynamics of simulated annealing placements, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.9, issue.3, pp.253-259, 1990.
DOI : 10.1109/43.46801

M. J. Rosenblatt, The Dynamics of Plant Layout, Management Science, vol.32, issue.1, pp.76-86, 1986.
DOI : 10.1287/mnsc.32.1.76

M. J. Rosenbfatt and H. L. Et-lee, A robustness approach to facilities design, International Journal of Production Research, vol.14, issue.4, pp.479-486, 1986.
DOI : 10.1080/00207548008919646

S. Sahni and T. Et-gonzalez, P-Complete Approximation Problems, Journal of the ACM, vol.23, issue.3, pp.555-565, 1976.
DOI : 10.1145/321958.321975

. Sechen, Chip-Planning, Placement, and Global Routing of Macro-cell lntegrated Circuits Using Simulated Annealing, International Journal of ComputerAided VLSI Design, vol.2, pp.127-158, 1990.

M. Scriabin and R. C. Et-vergin, A Cluster-Analytic Approach to Facility Layout, Management Science, vol.31, issue.1, pp.33-49, 1985.
DOI : 10.1287/mnsc.31.1.33

R. Sedgewick, Algorithmes en langage C, 1991.

J. M. Seehof and W. O. Et-evens, Automated layout design program, The Journal of Industrial Engineering, vol.18, issue.2, pp.690-695, 1967.
DOI : 10.1145/365719.366401

H. Seifoddini, Duplication Process in Machine Cells Formation in Group Technology, IIE Transactions, vol.21, issue.4, pp.382-388, 1989.
DOI : 10.1080/00207548608919736

P. Siarry and G. Et-dreyfus, La méthode du recuit simulé : théorie et applications, 1988.

N. Singh, Editorial, European Journal of Operational Research, vol.69, issue.3, pp.281-283, 1993.
DOI : 10.1016/0377-2217(93)90015-F

K. Y. Tam, A simulated annealing algorithm for allocating space to manufacturing cells, International Journal of Production Research, vol.30, issue.1, pp.63-87, 1992.
DOI : 10.1007/978-1-4613-1677-0

S. R. Tirumpatikumara, R. L. Kashyap, and C. L. Et-moodie, Artificial intelligence techniques in facilities layout planning : The development of an expert system, 1985.

J. A. Tompkins, R. Et-reed, and . Jr, An applied model for the facilities design problem, International Journal of Production Research, vol.9, issue.5, pp.583-595, 1976.
DOI : 10.1287/opre.19.1.124

T. Urban, A multiple criteria model for the facility layout problem, Journal Production Research, vol.25, issue.12, pp.183-193, 1981.

T. Urban, Computational performance and efficiency of lower-bound procedures for the dynamic facility layout problem, European Journal of Operational Research, vol.57, issue.2, pp.271-279, 1992.
DOI : 10.1016/0377-2217(92)90048-E

. Van, P. J. Laarhoven, and E. H. Et-aarts, Simulated annealing : Theory and Application, 1987.

H. J. Warnecke, R. Steinhilper, H. Roth, and T. Weber, Planning and Realization of FMS : Case studies, expeiences and recommendations, Fraunhofer Institute for Manufacturing Engineering and automation, 1981.

X. Xie, Manufacturing Cett Formation under Capacity Constraints, 1993.
DOI : 10.1002/asm.3150090203