Combinatorial optimisation algorithms for a CAD workstation (Q750305)

The application of random search algorithms for the solution of general assignment problems is discussed. Concrete examples of this problem such as layout of an electronic circuit, task scheduling, or minimizing the total length of a communication network are given. A concurrent version of the annealing algorithm of \textit{S. Kirkpatrick, C. D. Gelatt} and \textit{M. P. Vecchi} [``Optimization by simulated annealing. Quantitative studies'', Science 220(4598), 671--680 (1983; Zbl 1225.90162)] were realized by means of the OCCAM language and tested on a VAX 8600 computer. Results of comparative computational experiments are discussed. It is shown that a significant gain in speed (10 times) can be achieved by means of an accelerator incorporated parallel processing architecture (5 INMOS transputers were used). A decomposition procedure based on the minimum spanning tree and a random search algorithm for the solution of the layout problem are proposed.