Open AccessA branch and bound method in a permutation flow shop with blocking and setup times
Author(s) -
Marcelo Seido Nagano,
Mauricio Iwama Takano,
João Vítor Silva Robazzi
Publication year - 2022
Publication title -
international journal of industrial engineering computations
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.564
H-Index - 26
eISSN - 1923-2926
pISSN - 1923-2934
DOI - 10.5267/j.ijiec.2021.10.003
Subject(s) - tardiness , flow shop scheduling , permutation (music) , blocking (statistics) , computer science , upper and lower bounds , branch and bound , scheduling (production processes) , job shop scheduling , mathematical optimization , exploit , algorithm , parallel computing , mathematics , routing (electronic design automation) , embedded system , computer network , mathematical analysis , physics , acoustics , computer security
In this paper it is presented an improvement of the branch and bound algorithm for the permutation flow shop problem with blocking-in-process and setup times with the objective of minimizing the total flow time and tardiness, which is known to be NP-Hard when there are two or more machines involved. With that objective in mind, a new machine-based lower bound that exploits some structural properties of the problem. A database with 27 classes of problems, varying in number of jobs (n) and number of machines (m) was used to perform the computational experiments. Results show that the algorithm can deal with most of the problems with less than 20 jobs in less than one hour. Thus, the method proposed in this work can solve the scheduling of many applications in manufacturing environments with limited buffers and separated setup times.