Study On Rescheduling Method For Flow Shop Problem With Uncertainty

Flow shop is the simplified model of many actual production scheduling problems, and it is also a typical NP-complete problem. Previous works mostly focused on scheduling problems based on deterministic mathematical models with an assumption that the scheduling environment is ideal, thus there is a great gap between theory and practice of production scheduling. An in-depth study on rescheduling method for flow shop problem with uncertainty is progressed, and the two key elements which have influence on the performance of scheduling strategy are carefully investigated.Firstly, the scheduling methods are reviewed with the process of scheduling research. It is pointed out that heuristics still attract most attention.Secondly, the framework of dynamic scheduling research is under discussion, and the core problems of scheduling strategy are analyzed. For flow shop problem with uncertainty, a method based on insertion technique and event driven strategy is examined against benchmark programs. The results show great performance deterioration of some good heuristic in the face of uncertainty. The rescheduling policy and rescheduling method are the two keys for flow shop rescheduling. Then, it is found that rescheduling period is close to the arrival rate of jobs, and amethod is progressed to design appropriate rescheduling period. According rescheduling method, some job-insertion methods are discussed. Through the test against priority dispatching methods, the methods we progressed are good in both optimization performance and computer efficiency.Finally, conclusion is drawn and some future research directions are discussed.