Column Generation For Re-entrant Hybrid Flow-shop Scheduling Problem

As a typical manufacturing system in the semiconductor manufacturing,re-entrant manufacturing system industry has become a research hotspot.Some system with similar re-entrant characteristics were also found in the fields of computer network,communication network and steel pipe industry.The concept of re-entrant has a significant impact on modern technology.Because of re-entrant characteristics,the complexity of the processing route and high machine utilization,the traditional theories and methods of flow-shop and job-shop are no longer applicable for re-entrant manufacturing system.Machine scheduling is an important behavior of the production system.Re-entrant hybrid flow-shop is a typical re-entrant manufacturing system,the research on its scheduling problem is an important project of re-entrant manufacturing system scheduling problem,which has a very important theoretical and economic significance.The research of re-entrant hybrid flow-shop scheduling problem is mainly focused on modeling and solving at present which is very difficult because of the complexity.The research of re-entrant hybrid flow-shop scheduling problem is growing up.Column generation algorithm has an excellent performance in traditional machine scheduling problem recently.However,there is no research application column generation algorithm to re-entrant hybrid flow-shop scheduling problem.This is the first paper which use the column generation algorithm on re-entrant hybrid flow-shop scheduling problem,and we did a lot of exploratory work to study the effect of column generation algorithm to solve such problems.A scheduling model of RHFS with consideration of re-entrant property was built based on the traditional Integer model of hybrid flow-shops.The new model was reformulated as a set partitioning model including job-level sub-problems by Dantzig-Wolfe decomposition,and then the decomposed models were solved by column generation algorithm.The numerical studies showed that the rationale of the new model of RHFS and the solving algorithm which based on column generation had good performance on accuracy and efficiency.And some exploratory work was completed based on the numerical studies.