Exact exponential algorithms for 3-machine flowshop scheduling problems |
| |
Authors: | Lei Shang Christophe Lenté Mathieu Liedloff Vincent T’Kindt |
| |
Affiliation: | 1.Laboratoire d’Informatique (EA 6300), ERL CNRS OC 6305,Université Fran?ois-Rabelais de Tours,Tours,France;2.INSA Centre Val de Loire, LIFO EA 4022,Université d’Orléans,Orléans,France |
| |
Abstract: | In 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 ({mathcal {O}}^*(3^n)) is proposed, which improves the current best-known time complexity (2^{{mathcal {O}}(n)}times Vert IVert ^{{mathcal {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 (F3Vert f_mathrm{max}) and (F3Vert sum f_i) problems, is discussed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|