Title: A modified column generation heuristic for hybrid flow shop multiple orders per job scheduling problem

Authors: Bing-Hai Zhou; Wen-Long Liu

Addresses: School of Mechanical Engineering, Tongji University, Shanghai, China ' School of Mechanical Engineering, Tongji University, Shanghai, China

Abstract: With a comprehensive consideration of multiple product types, sequence-dependent setup time constraints and two different processing modes in wafer fabrication process, a scheduling model of multiple orders per job in a hybrid flow shop with an objective function of minimising total completion time of the system is developed. On the basis of the description, a new column generation algorithm based on a three-level (job-product-machine) disjunctive network flow is put forward. Furthermore, in order to improve degradation effects of the algorithm, a Lagrangian relaxation with sub-gradient optimisation is integrated into a frame of the column generation algorithm. Therefore, a modified column generation algorithm as a combination of Lagrangian approach and column generation algorithm is proposed. Finally, theory analysis and simulation experiments demonstrate that the presented algorithm is valid and feasible.

Keywords: multiple product types; sequence-dependent setup time; disjunctive network flow; modified column generation algorithm.

DOI: 10.1504/IJMTM.2019.100166

International Journal of Manufacturing Technology and Management, 2019 Vol.33 No.1/2, pp.88 - 113

Received: 26 Jun 2017
Accepted: 19 Jan 2018
Published online: 14 Jun 2019 *

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