Abstract:With a comprehensive consideration of multiple product types and sequence-dependent setup times constraints in which processes of wafer fabrications, a scheduling model of multiple orders per job(MOJ) in a hybrid flow shop with an objective function of minimizing total completion time of the system is developed. On the basis of the descriptions, a column generation algorithm based on the job-product-machine three level disjunctive network flow is proposed. Furthermore, to improve the degradation effects of column generation algorithm, Lagrangian relaxation with sub-gradient optimization is combined into the frame of column generation algorithm, and then a modified column generation(MCG) algorithm adopting dual iteration is proposed. Finally, theory analysis and simulation experiments show that the developed MCG algorithm is valid and feasible.