Exact exponential algorithms for 3-machine flowshop scheduling problems

摘要

AbstractIn 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, aDynamic Programmingalgorithm running in$${mathcal {O}}^*(3^n)$$O∗(3n)is proposed, which improves the current best-known time complexity$$2^{{mathcal {O}}(n)}times Vert IVert ^{{mathcal {O}}(1)}$$2O(n)×‖I‖O(1)in the literature. The idea is based on a dominance condition and the consideration of thePareto Frontin the criteria space. The algorithm can be easily generalized to other problems that have similar structures. The generalization on two problems, namely the$$F3Vert f_mathrm{max}$$F3‖fmaxand$$F3Vert sum f_i$$F3‖∑fiproblems, is discussed.