There Stage Flexible Flowshop With Identical Processor And Batch Machine

This paper considers a three-stage flexible flowshop scheduling problem that consists of m identical machines at stage 1, one batch processor at stage 2 and the other batch processor at stage 3. The objective is to minimize the makespan. This paper is divided into six chapters:The basic knowledge of scheduling, the problems and results are introduced in the first chapter.The case of that all jobs have the same processing time at stage 1, at stage 2 and at stage 3, respectively, is studied in the second chapter. We get algorithm of general situation in ( )1O n B time and algorithms of some kinds of special situations in O(n) time.The case of that all jobs have arbitrary processing time at stage 1 but have same processing time at stage 2 and stage 3 independently is studied in the third chapter. We get conclusion that the problem is NP-hard except 4 kinds of special cases, where 2 kinds of special cases are polynomial solvable and the complexities of 2 kinds of special cases are open. For the general case, an approximation algorithm H3.1 whose performance ratio satisfying H 3.1R <2 is presented; for 13 kinds of special cases, we give 2 optimal algorithms in O(nlog n) time and 4 approximation algorithms whose performance ratio are not more than (2 -1 m).The case of that all jobs have same processing time at stage 1 and stage 2 independently but have arbitrary processing time at stage 3 is researched in the fourth chapter. The problem is divided into 3 kinds to discuss: the first two kinds are proved to be solvable in polynomial time, the last kind gives a polynomial time approximation algorithm and its performance ratio and numerical simulations. For the general case, then we get a polynomial time approximation algorithm with performance ratio being not more than 2.The case of that all jobs have same processing time at stage 1 and stage 3 independently but have arbitrary processing time at stage 2 is analyzed in the fifth chapter. We give two polynomial time approximation algorithms and their performance ratios and numerical simulations.In the sixth chapter, we summarize the conclusions obtained in this paper and then analyze the defect of this paper and show the further work which can be done.