Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times

• We consider a two-machine flowshop problem with a limited waiting time constraint.
• We develop a branch-and-bound algorithm with new lower bounds and upper bounds.
• A lower bound obtained from Kruskal’s algorithm is more effective than others.
• Proposed dominance properties help to reduce computation time to solve the problem.

We consider a two-machine flowshop scheduling problem in which jobs should be processed on the second machine within a certain period of time after those jobs are completed on the first machine, and sequence-dependent setup times are required on the second machine. For the problem with the objective of minimizing makespan, we develop several dominance properties, lower bounds, and heuristic algorithms, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test instances. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 30 jobs in a reasonable amount of CPU time.