Exact algorithms to flowshop scheduling with sequence-dependent set-up times

Flowshop scheduling with sequence-dependent set-up times (FSSDST) is widely encountered in process manufacturing industries with high complexity. The paper studies the permutation FSSDST problem in which the objective is to minimize the makespan. The MILP formulation of the FSSDST is developed firstly. Then, two methods to determine the lower bound of FSSDST are proposed: (1) The method based on the last machine (LB1); (2) The method based on all the machines (LB2). Based on these two methods, two branch-and-bound algorithms are developed and performed. The two upper bound's improvement methods are proposed to increase the branch-and-bound algorithms' efficiency: (1) modified initial upper bound; (2) modified dynamic upper bound. All above algorithms are implemented. Experiments on randomly generated problems are performed to identify the performances of the proposed new methods.