Exact exponential algorithms for 3-machine flowshop scheduling problems

International audienceIn this paper, we focus on the design of an exact exponential time algorithm with a proved worst-case running time for 3-machine flowshop scheduling problems considering worst-case scenarios. For the minimization of the makespan criterion, a Dynamic Programming algorithm running in O∗(3n)O∗(3n) is proposed, which improves the current best-known time complexity 2O(n)×∥I∥O(1)2O(n)×‖I‖O(1) in the literature. The idea is based on a dominance condition and the consideration of the Pareto Front in the criteria space. The algorithm can be easily generalized to other problems that have similar structures. The generalization on two problems, namely the F3∥fmaxF3‖fmax and F3∥∑fiF3‖∑fi problems, is discussed