E. H. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines, J. and Sons, 1988.

B. S. Baker and E. G. Coffman, A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing, SIAM Journal on Algebraic Discrete Methods, vol.2, issue.2, pp.147-152, 1981.
DOI : 10.1137/0602019

J. Beardwood, J. Halton, and J. Hammersley, The shortest path through many points, Proc. Camb, pp.299-327, 1959.
DOI : 10.2307/2031707

X. Berenguer, A characterization of linear admissible transformations for the m-travelling salesmen problem, European Journal of Operational Research, vol.3, issue.3, pp.232-249, 1979.
DOI : 10.1016/0377-2217(79)90143-7

D. Bertsimas, Probabilistic combinatorial optimization problems, Operations Research Center. MIT. Cambridge. Mass, 1988.

D. Bertsimas, The probabilistic minimum spanning tree problem, Networks, vol.18, issue.3, pp.245-275, 1990.
DOI : 10.1002/net.3230200302

D. Bertsimas, A Vehicle Routing Problem with Stochastic Demand, Operations Research, vol.40, issue.3, 1992.
DOI : 10.1287/opre.40.3.574

D. Bertsimas and L. Howell, Further results on the probabilistic travelling salesman problem, MIT Sloan School of Management Working paper, pp.2066-88, 1988.

D. Bertsimas, P. Jaillet, and A. Odoni, A Priori Optimization, Operations Research, vol.38, issue.6, pp.1019-1033, 1990.
DOI : 10.1287/opre.38.6.1019

E. Bonomi and J. L. Lutton, -City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Review, vol.26, issue.4, pp.551-568, 1984.
DOI : 10.1137/1026105
URL : https://hal.archives-ouvertes.fr/inria-00440395

J. Bruno, E. G. Coffman, and R. Sethi, Scheduling indépendant tasks to reduce mean finishing time, Communications of the ACM, vol.17, issue.7, 1974.
DOI : 10.1145/361011.361064

J. Carlier and P. Chrétienne, Un domaine tr??s ouvert : les probl??mes d'ordonnancement, RAIRO - Operations Research, vol.16, issue.3, pp.175-217, 1982.
DOI : 10.1051/ro/1982160301751
URL : http://archive.numdam.org/article/RO_1982__16_3_175_0.pdf

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. Chang, R. Nelson, and M. Pinedo, Scheduling two classes of exponential jobs on parallel processors: structural results and worst-case analysis, Advances in Applied Probability, vol.29, issue.04, pp.925-944, 1991.
DOI : 10.1145/322234.322242

P. Chervi, A computational approach to probabilistic vehicle routing problems, MIT, Master of Science in Operations Research, 1990.

E. G. Coffman, G. S. Lueker, and A. H. Kan, Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics, Management Science, vol.34, issue.3, pp.266-290, 1988.
DOI : 10.1287/mnsc.34.3.266

E. G. Coffman, Computer and Job-Shop Scheduling Theory, J. and Sons, 1976.

R. W. Conway, W. L. Maxwel, and L. W. Miller, Theory of scheduling, 1970.

G. Cornuèjols and G. L. Nemhausser, Tight bounds for christofides' traveling salesman heuristic, Mathematical Programming, vol.14, issue.1, pp.116-121, 1978.
DOI : 10.1007/BF01588956

W. L. Eastman, S. Even, and I. M. Isaacs, Bounds for the optimal scheduling of n jobs on m processors, Management Sei, vol.11, issue.2, pp.268-279, 1964.

W. Feller, An Introduction to Probability Theory and its Applications, II. Wiley, J, and Sons, 1971.

L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Journal canadien de math??matiques, vol.8, issue.0, p.399, 1956.
DOI : 10.4153/CJM-1956-045-5

G. N. Frederickson, Probabilistic analysis for simple one-and two-dimensional bin packing algorithms, Information Processing Letters, vol.11, issue.4-5, pp.156-161, 1980.
DOI : 10.1016/0020-0190(80)90041-1

E. Y. Gabovitch, The small traveling salesman problem. Trudy vychisl, Tsentra Tratu. Gos. Univ, vol.19, pp.27-51, 1970.

M. R. Garey and D. S. Johnson, Computers and Intractability : a Guide to the Theory of NP-completeness, 1978.

K. D. Giazebrook, Scheduling tasks with exponential service times on parallel processors, Journal of Applied Probability, vol.38, issue.03, pp.685-689, 1979.
DOI : 10.2307/3213411

F. Glover, Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, vol.13, issue.5, pp.533-549, 1986.
DOI : 10.1016/0305-0548(86)90048-1

M. Gondran and M. Minoux, Graphes et Algorithmes, 1979.

R. L. Graham, Bounds for Certain Multiprocessing Anomalies, Bell System Technical Journal, vol.45, issue.9, pp.1563-1581, 1966.
DOI : 10.1002/j.1538-7305.1966.tb01709.x

R. L. Graham, Bounds on Multiprocessing Timing Anomalies, SIAM Journal on Applied Mathematics, vol.17, issue.2, pp.416-419, 1969.
DOI : 10.1137/0117039
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.8131

M. Held and R. Karp, A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, vol.10, issue.1, pp.196-210, 1962.
DOI : 10.1137/0110015

E. Horowitz and S. Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM, vol.21, issue.2, pp.277-292, 1974.
DOI : 10.1145/321812.321823

E. Horowitz and S. Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM, vol.23, issue.2, pp.317-327, 1976.
DOI : 10.1145/321941.321951

P. Jaillet, Probabilistic traveling salesman problem, Technical Report Operations Research Center. MIT. Cambridge. Mass, vol.185, 1985.

P. Jaillet, Analysis of the probabilistic traveling salesman problem in the plane, Ricerca Operativa, vol.36, 1986.

P. Jaillet, Stochastic routing problems, Stochastics in Combinatorial Optimization, 1987.

P. Jaillet, On Some Probabilistic Combinatorial Optimization Problems Defined on Graphs, Flow Control of Congested Network, 1987.
DOI : 10.1007/978-3-642-86726-2_16

P. Jaillet, A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited, Operations Research, vol.36, issue.6, pp.929-936, 1988.
DOI : 10.1287/opre.36.6.929

P. Jaillet, Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems, Mathematics of Operations Research, vol.17, issue.4, pp.964-980, 1992.
DOI : 10.1287/moor.17.4.964

P. Jaillet, Shortest path problems with node failures. Networks, pp.589-605, 1992.
DOI : 10.1002/net.3230220607
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.650.4200

P. Jaillet, Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces, Mathematics of Operations Research, vol.18, issue.1, 1993.
DOI : 10.1287/moor.18.1.51

D. S. Johnson, Fast algorithms for bin packing, Journal of Computer and System Sciences, vol.8, issue.3, pp.272-314, 1974.
DOI : 10.1016/S0022-0000(74)80026-7

D. S. Johnson, C. Aragon, L. A. Mcgeoch, and C. Schevon, Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, Operations Research, vol.37, issue.6, pp.865-892, 1989.
DOI : 10.1287/opre.37.6.865

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM Journal on Computing, vol.3, issue.4, pp.298-325, 1974.
DOI : 10.1137/0203025

T. Kampke, Optimal Scheduling of Jobs with Exponential Service Times on Identical Parallel Processors, Operations Research, vol.37, issue.1, pp.126-133, 1989.
DOI : 10.1287/opre.37.1.126

R. M. Karp, Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane, Mathematics of Operations Research, vol.2, issue.3, pp.209-224, 1977.
DOI : 10.1287/moor.2.3.209

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

W. Knödel, A bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit, 10th Symposium, pp.369-378, 1981.
DOI : 10.1007/3-540-10856-4_104

E. L. Lawler, J. K. Lenstra, A. H. Kan, and D. B. Shmoys, The Traveling Salesman Problem, 1985.

T. G. Lewis and H. El-rewini, Introduction to Parallel Computing, 1992.

G. S. Lueker, An average-case analysis of bin packing with uniformly distributed item sizes, 1982.

G. S. Lueker and E. G. Coffman, Probabilistic Analysis of Packing and Partitionning algorithms, discrete Mathematics and optimization, 1991.

M. Lundy and A. Mees, Convergence of an annealing algorithm, Mathematical Programming, vol.2, issue.5, pp.111-124, 1986.
DOI : 10.1007/BF01582166

R. H. Mohring, F. J. Radermacher, and G. Weiss, Stochastic scheduling problems II-set strategies-, Zeitschrift f??r Operations Research, vol.17, issue.7, pp.65-104, 1980.
DOI : 10.1007/BF01918198

C. A. Morgenster and H. D. Shapiro, Chromatic number approximation using simulated annealing, 1986.

T. W. Rhee, Probabilistic analysis of the next fit decreasing algorithm for bin-packing, Operations Research Letters, vol.6, issue.4, pp.189-191, 1987.
DOI : 10.1016/0167-6377(87)90018-6

S. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM, vol.23, issue.1, pp.116-127, 1976.
DOI : 10.1145/321921.321934

G. H. Sasaki and B. Hajek, The time complexity of maximum matching by simulated annealing, Journal of the ACM, vol.35, issue.2, pp.387-403, 1988.
DOI : 10.1145/42282.46160

J. Steele, Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability, The Annals of Probability, vol.9, issue.3, pp.365-376, 1981.
DOI : 10.1214/aop/1176994411

G. Weiss and M. L. Pinedo, Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions, Journal of Applied Probability, vol.17, issue.01, pp.187-202, 1980.
DOI : 10.1214/aoms/1177699369