A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems

Marcus Randall, David Abramson

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

Tahu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation of TS can represent a significant saving in the real-time required to solve a problem over an equivalent sequential algorithm. In this study, a general parallel TS algorithm for solving combinatorial optimisation problems (COPs) is presented. The unique feature of our approach is that the TS solves a wide range of COPs expressed in a high level syntax. The benefit of this general code is that it can be used in real-time applications due to its parallel scala­bility and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are pre­sented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.
Original languageEnglish
Title of host publicationPART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999
EditorsWilson C. H. Cheng, A. S. M. Sajeev
Place of PublicationSingapore
PublisherSpringer
Pages68-79
Number of pages12
ISBN (Print)9814021598
Publication statusPublished - 1999

    Fingerprint

Cite this

Randall, M., & Abramson, D. (1999). A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. In W. C. H. Cheng, & A. S. M. Sajeev (Eds.), PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999 (pp. 68-79). Singapore: Springer.