LAUSR

Abstract This work addresses the minimization of the makespan criterion for the permutation flow shop problem with blocking, sequence and machine dependent setup times, which is a problem that has not been studied in previous works. Many papers considered the problem with an unlimited buffer or with the setup time embedded in the processing time of the job. However, considering an unlimited buffer may not represent reality in many industries. Additionally, separating the setup time from the processing time allows greater flexibility for production scheduling, thus allowing better time usage and a reduction in the makespan. Two structural properties of the problem are presented: an upper bound for the machine idle time and a lower bound for the machine blocking time. Using these properties, four lower bounds for the makespan are proposed (LBTN1, LBTN2, LBTN3 and LBTN4). Each of the lower bounds was used in a branch-and-bound algorithm and then compared to each other using a database containing 540 problems. A MILP model is also presented and compared with the best of the branch-and-bound models using a second database that consists of 80 different problems. Computational tests are presented, and the comparisons indicate that the proposed lower bounds are promising.