¹Wroclaw University of Technology, Wroclaw, Poland

Correspondence: J Grabowski, Institute of Engineering Cybernetics, Wrocaw University of Technology, Janiszewskiego 11–17, 50-372 Wrocaw, Poland. E-mail: grabow@ict.pwr.wroc.pl

Received July 1999; Accepted August 2000.

Abstract

This paper deals with the classic flow-shop scheduling problem with the make-span criterion. Some new properties of the problem associated with the so-called blocks have been presented and discussed. The properties allow us to skip some non-perspective solutions during the search of the solution space. Applied to local search algorithms, they result in a significant reduction of neighbourhood size and quickly direct the search trajectory to promising regions of the solution space. The implementation of the proposed properties in a tabu search algorithm is also presented. Computational experiments (up to 500 jobs and 20 machines) are given and compared with the results yielded by the best known algorithms.