A branch and bound algorithm for two-stage hybrid flow shop scheduling: minimizing the number of tardy jobs

This paper considers a two-stage hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation and sequence of jobs at each stage. A branch and bound algorithm that gives the optimal solutions is suggested that incorporates the methods to obtain the lower and upper bounds. Dominance properties are also suggested to reduce the search space. To show the performance of the algorithm, computational experiments are done on randomly generated problems, and the results are reported.