New block properties for the permutation flow shop problem with application in tabu search

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.