A modified column generation heuristic for hybrid flow shop multiple orders per job scheduling problem. (11th June 2019)

• Record Type: Journal Article
• Authors: Zhou, Bing-Hai; Liu, Wen-Long
• Is Part Of: International journal of manufacturing technology and management. Volume 33:Number 1/2(2019)
• Page Start: 88
• Page End: 113
• Publication Date: 2019-06-11
• Subjects: multiple product types -- sequence-dependent setup time -- disjunctive network flow -- modified column generation algorithm; Manufacturing processes -- Periodicals; Manufacturing processes -- Automation -- Periodicals; Production management -- Periodicals; 670.427068
• Languages: English
• ISSNs: 1368-2148

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.