Reentrant permutation flow shop problems: definitions and heuristics

Abstract In a flow shop, jobs are serially processed on a set of machines and the machine order is the same for all the jobs. In a permutation flow shop, there is an additional assumption that the order in which jobs enter the machines is the same on each machine. While the meaning of "permutation" is clear for a flow shop, it is more ambiguous for a reentrant flow shop. In a reentrant flow shop, jobs are processed on some machines more than once, leading to several ways of understanding the meaning of permutation. We indicate that different researchers use the term permutation for different assumptions. We clear up this ambiguity by identifying four definitions of permutation scheduling in the context of reentrant permutation flow shops with the cyclic pattern. In addition, we analyze the impact of these definitions on optimization and on heuristic performance with respect to the makespan objective function. We first compare optimal solutions across different permutation types, identifying cases where the best solution follows a specific permutation structure. We then extend known permutation flow shop heuristics to all four permutation definitions. Through computational experiments, we evaluate the effectiveness of these heuristics.