On the heuristic solution of the permutation flow shop problem by path algorithms

This paper considers the classical permutation flow shop problem from machine scheduling. The problem is NP-hard. Therefore, methods such as local search or simulated annealing are often applied for the heuristic solution. The paper develops fast iterative methods which generate a restricted number of paths in a particular neighbourhood represented by a special shift graph. To generate the paths several structural properties are used with respect to the path structure of a feasible solution (i.e. the longest path in a network and lower bounds resulting from this path structure). This makes the algorithm very efficient. A comparison with other well-known methods is made. The proposed algorithm also out performs different variants of simulated annealing and tabu search.