Parallel tabu search approaches for two-dimensional cutting

Abstract

A tabu search based approach is studied as a method for solving in parallel the two-dimensional irregular cutting problem. We use and compare different, variants of the method and various parallel computing systems. Systems used are based on message passing or shared memory paradigm. Parallel algorithms using both methods of communication are proposed. The efficiency of computer system utilization is discussed in the context of unpredictable time requirements of parallel tasks. We present results for different variants of the method together with efficiency measures for parallel implementations, where IBM SP2 and CRAY T3E systems, respectively, have been used.