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

Authors: Kazuko Morizawa, Xi Sun, Hiroyuki Nagasawa

Addresses: Department of Industrial Engineering, Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Sakai, Osaka, 599-8531, Japan. Department of Industrial Engineering, Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Sakai, Osaka, 599-8531, Japan. Department of Industrial Engineering, Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Sakai, Osaka, 599-8531, Japan

Abstract: 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.

Keywords: scheduling; machining-assembly flowshop; heuristic; branch and bound algorithm; parallel search; makespan.

DOI: 10.1504/IJMTM.2003.002526

International Journal of Manufacturing Technology and Management, 2003 Vol.5 No.1/2, pp.20-27

Published online: 19 Jul 2003 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article