×

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

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
PDF BibTeX XML Cite
Full Text: DOI

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, () · 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)
[13] Price, C.C., The assignment of computational tasks among processors in a distributed system, (), 291-296
[14] Price, C.C.; Garner, J.M., Task assignment modelled as a quadratic programming problem, ()
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.