Squeezing branch and bound algorithm for the machine-fixed, machining-assembly flowshop scheduling problem

摘要

This paper proposes a squeezing branch and bound (squeezing B&B) algorithm for solving the machine-fixed, machining-assembly flowshop scheduling problem to minimise makespan. The squeezing B&B is a B&B-based heuristic algorithm which searches for a pre-specified number of promising nodes in parallel at each branching level and terminates the search without any backtracking when the branching tree reaches to the bottom level. Since the squeezing B&B selects parent nodes according to the minimum lower bound rule, a tight lower bound and a dominance rule are also proposed and incorporated into the squeezing B&B for searching a near-optimal schedule more effectively. Numerical experiments are implemented to demonstrate that the proposed method is useful for efficiently obtaining the optimal or near-optimal schedule within a reasonable computation time.