The flow shop with parallel machines: A tabu search approach

A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a flow shop with parallel machines is presented. The algorithm is based on a tabu search technique with a specific neighborhood definition which employs notions of a critical path in a graph and a block of jobs. This is the first improvement algorithm for the considered problem. A special advanced method of implementation improves the local search significantly and increases the speed of the algorithm. Computational experiments (up to 3000 operations and 60 machines) show its excellent numerical properties. The proposed approach can be used for modeling and solving a broad class of flexible flow line scheduling problems.