A branch-and-bound method to minimize the makespan in a permutation flow shop with blocking and setup times

Cogent Engineering

Mauricio Iwama Takano¹  Marcelo Seido Nagano² 

[1] Federal Technological University - Paraná;University of São Paulo;

关键词: flow shop;    blocking;    zero buffer;    setup times;    makespan;    lower bound;    branch–and-bound;    milp;   

DOI  :  10.1080/23311916.2017.1389638

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown