A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities

We investigate the problem of scheduling N jobs on parallel machines in L successive stages with limited buffer capacities between stages. The primary objective is to find a schedule that would minimize the makespan. This problem is shown to be NP-hard in the strong sense. We develop a tabu search algorithm for this problem in which the search is limited to the space of permutation vectors of size N. This vector represents the order in which the given set of jobs are performed in the first stage, and we propose a procedure to construct a complete schedule associated with every permutation vector. We conduct an extensive computational experiment using randomly generated instances with different structures and different buffer capacities. We also solve several specific instances of the problem from the open literature. All empirical evidence suggest that the proposed algorithm is an effective method for solving this problem. (C) 2003 Elsevier B.V. All rights reserved.