The literature on flow shop scheduling has extensively analyzed two classes of problems: permutation and non-permutation ones (PFS and NPFS). Most of the papers in this field have been just devoted on comparing the solutions obtained in both approaches. Our contribution consists of analyzing the structure of the critical paths determining the makespan of both kinds of schedules for the case of 2 jobs and m machines. We introduce a new characterization of the critical paths of PFS solutions as well as a decomposition procedure, yielding a representation of NPFS solutions as sequences of partial PFS ones. In structural comparisons we find cases in which NPFS solutions are dominated by PFS solutions. Numerical comparisons indicate that a wider dispersion of processing times improves the chances of obtaining optimal non-permutation schedules, in particular when this dispersion affects only a few machines.

Industry 4.0 is a modern approach that aims at enhancing the connectivity between the different stages of the production process and the requirements of consumers. This paper addresses a relevant problem for both Industry 4.0 and flow shop literature: the missing operations flow shop scheduling problem. In general, in order to reduce the computational effort required to solve flow shop scheduling problems only permutation schedules (PFS) are considered, i.e., the same job sequence is used for all the machines involved. However, considering only PFS is not a constraint that is based on the real-world conditions of the industrial environments, and it is only a simplification strategy used frequently in the literature. Moreover, non-permutation (NPFS) orderings may be used for most of the real flow shop systems, i.e., different job schedules can be used for different machines in the production line, since NPFS solutions usually outperform the PFS ones. In this work, a novel mathematical formulation to minimize total tardiness and a resolution method, which considers both PFS and (the more computationally expensive) NPFS solutions, are presented to solve the flow shop scheduling problem with missing operations. The solution approach has two stages. First, a Genetic Algorithm, which only considers PFS solutions, is applied to solve the scheduling problem. The resulting solution is then improved in the second stage by means of a Simulated Annealing algorithm that expands the search space by considering NPFS solutions. The experimental tests were performed on a set of instances considering varying proportions of missing operations, as it is usual in the Industry 4.0 production environment. The results show that NPFS solutions clearly outperform PFS solutions for this problem.