The paper investigates the combinatorial structure of the n/m/P/Cmax permutation flow shop problem. To each solution (a permutation of n elements) it introduces a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network the paper derives combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the considered problem. For several neighbourhood structures it calculates the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement.
