A branch-and-bound algorithm for two-stage no-wait hybrid flow-shop scheduling

Abstract

This research investigates a two-stage no-wait hybrid flow-shop scheduling problem in which the first stage contains a single machine, and the second stage contains several identical parallel machines. The objective is to minimise the makespan. For this problem, existing literature emphasises on heuristics or optimal solutions for special cases, whereas this paper proposes a branch-and-bound algorithm. Several lower bounds for optimal and partial schedules are derived. Also, three dominance rules are deduced, and seven constructive heuristics are used to obtain initial upper bounds. Extensive computational tests on randomly generated problems are conducted. The results with comparisons indicate that the proposed bounds (especially partial lower bounds), dominance rules and the branch-and-bound algorithm are efficient.