Parallel Tabu Search Method Approach for Very Difficult Permutation Scheduling Problems

There are very many issues, where scheduling can be applied, in computer systems (single and multiprocessors) as well as in production systems. Scheduling problems belongs in most cases to NP-hard class. For most of classical scheduling problems, published in last 10 years (for example benchmarks of Taillard [Benchmarks for basic scheduling problems] for the flow shop problem), there are still no optimal solutions. In this paper we propose very effective method of construct parallel algorithms based on tabu search metaheuristic. We apply block properties, which enable parallel algorithm to distribute calculations and reduce communication between processors. Algorithms are implemented in Ada95 and MPI.