On the combinatorial structure of the permutation flow shop problem

What is it about?

The combinatorial structure of the permutation flow shop problem is investigated. To each permutation we introduce a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network, we derive combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the problem under consideration. For several neighbourhood structures the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement is determined.

Featured Image