Combinatorial optimisation algorithms for a CAD workstation

DOI10.1016/0166-218X(90)90102-IMaRDI QIDQ750305zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(90)90102-i

zbMATH Keywords

annealingcomputational experimentsdecompositionlayout of an electronic circuitminimum spanning treeparallel processing architecturerandom search algorithmstask scheduling

Mathematics Subject Classification ID

Distributed algorithms (68W15) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Applications of mathematical programming (90C90)

Review text

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.

Recommendations

• Optimization by simulated annealing
• A parallel simulated annealing algorithm
• Assignment of program modules to processors: a simulated annealing approach.
• Solving VLSI physical design problems on a vector machine
• scientific article; zbMATH DE number 724213

Cites work

• Global optimization algorithms for a CAD workstation
• scientific article; zbMATH DE number 3799403 (Why is no real title available?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimization by simulated annealing
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• The Complexity of Flowshop and Jobshop Scheduling

Cited in

(1)

• Global optimization algorithms for a CAD workstation

This page was built for publication: Combinatorial optimisation algorithms for a CAD workstation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q750305)