The impact of missing operations on the flow shop: permutation vs. non permutation modes

¹ Département d’informatique et de mathématique, Université du Québec à Chicoutimi, Saguenay, Québec, Canada
² Département de mathématiques et de génie industriel, École Polytechnique Montréal, Montréal, Québec, Canada

^* Corresponding author: randa.ouchene1@uqac.ca

Received: 26 December 2023
Accepted: 24 March 2025

Abstract

The flow shop scheduling problem is traditionally studied under the assumption that the optimal solution is a permutation schedule. However, for many practical problems, this may not be the case. Since finding a flow shop schedule is significantly simpler with the permutation consideration restrection, it becomes interesting to know a priori at what extent relaxing this constraint could be beneficial. In this paper, we study the conditions under which this assumption holds, particularly in flow shops with missing operations. We focus our analysis on the makespan and total completion time. Preliminary results show that, in certain cases, non-permutation schedules can yield significantly better outcomes.