Simulated annealing applied to the process allocation problem. (English) Zbl 0760.90080

Sofianopoulou, Stella

Eur. J. Oper. Res. 60, No. 3, 327-334 (1992).

Summary: Simulated annealing is a stochastic optimization method based on iterative improvement with ‘controlled’ deteriorations of the objective function in order to escape local minima. The heuristic is based on an analogy between problems in combinatorial optimization and statistical mechanics. This paper presents an application of the simulated annealing method to the process allocation problem which consists of allocating a number of communicating processes to a network of processors. Computational results of a set of random problems which have similar characteristics to a real world telecommunications problem are also presented.

MSC:

90C27	Combinatorial optimization
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

simulated annealing; heuristics; process allocation; network of processors; real world telecommunications

References:

[1]	Aarts, E. H.L.; Van Laarhoven, P. J.M., Statistical cooling: A general approach to combinatorial optimization problems, Philips and Journal of Research, 40, 193-226 (1985)
[2]	Burkard, R. E.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17, 169-174 (1984) · Zbl 0541.90070
[3]	Collins, N. E.; Eglese, R. W.; Golden, B. L., Simulated annealing - An annotated bibliography, American Journal of Mathematical and Management Science, 8, 209-307 (1988) · Zbl 0669.65047
[4]	Connolly, D. T., An improved annealing scheme for the QAP, European Journal of Operational Research, 46, 93-100 (1988) · Zbl 0715.90079
[5]	Eglese, R. W., Simulated annealing: A tool for operational research, European Journal of Operational Research, 46, 271-281 (1990) · Zbl 0699.90080
[6]	Golden, B. L.; Skiscim, C. C., Using simulated annealing to solve routing and location problems, Naval Research Logistics Quarterly, 33, 261-279 (1986) · Zbl 0593.90054
[7]	Hajek, B., Cooling schedules for optimal annealing, Mathematics of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[8]	Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation; Part I, Graph partitioning, Operations Research, 37, 865-892 (1989) · Zbl 0698.90065
[9]	Kirkpatrick, F.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[10]	Lundy, M., The annealing algorithm and global optimization, (Ph.D. Thesis (1984), University of Cambridge) · Zbl 0581.90061
[11]	Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 34, 111-124 (1986) · Zbl 0581.90061
[12]	Metropolis, N.; Rosenbluth, A. W.; Teller, A. H.; Teller, E., Equation of state calculation by fast computing machines, Journal of Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006
[13]	Price, C. C., The assignment of computational tasks among processors in a distributed system, (Proceedings of the AFIPS National Computer Conference (1981)), 291-296
[14]	Price, C. C.; Garner, J. M., Task assignment modelled as a quadratic programming problem, (Report DMS-7 (1983), Dept. of Maths and Stats, Stephen F. Austin State University: Dept. of Maths and Stats, Stephen F. Austin State University Texas)
[15]	Sofianopoulou, S., Optimum allocation of process in a distributed environment: A process-to-process approach, Journal of the Operational Research Society, 41, 329-337 (1990) · Zbl 0707.90033