Many traditional algorithmic techniques used in combinatorial optimization have reached the computational limits of their scope. A relatively low cost and availability of parallel multi-core clusters offer a potential opportunity to shift these limits. Unfortunately, most existing serial algorithms are not easily adaptable to parallel computing systems. The objective of this work is to provide new algorithmic methods that can be easily and effectively scaled to parallel systems with large numbers of processing units. We concentrate on a scalability that comes from running a set of independent algorithms in parallel. We investigate the relationship between the parallel acceleration and properties of serial algorithms. Some of these results revealed that the best serial algorithm is not necessarily the best choice in parallel setting. Additionally, we observed that the combination of different algorithms (some of them may have poor performance characteristics!) can be more beneficial then using any particular algorithm on its own. The limitations of this approach are addressed.;In this dissertation, we present the algorithms based on Global Equilibrium Search method and Tabu Search method for classical optimization problems. These algorithm demonstrate the state-of-the-art performance comparing to the latest published work in the field: Unconstrained Binary Quadratic Problem, Weighted MAX-SAT problem and Job Shop Scheduling Problem. (Full text of this dissertation may be available via the University of Florida Libraries web site. Please check http://www.uflib.ufl.edu/etd.html)
展开▼
