View article

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that …