A Class Of Flexiable Two-stage Flowshop With Parallel And Burn-in Processor

This paper study the flexiable two-stage flowshop scheduling problem with m identical ( dedicated ) parallel machines in one stage and a batch processor in another stage. The organization of this paper is as follows:In Chapter 1, we describe scheduling theory and complexity simply, introduce research results for the FSMP ( Flow Shop with Multiple Processors ) problem F2 || f and BI (Burn In) problem 1 | BI | f, respectively. Then we introduce in problem F2 (· , ·) | BI | C_max, notation and results etc. ( cf. Table 1.1 ～ Table 1.4 ).In Chapter 2, we investigate the flexiable two-stage flowshop scheduling problem. In this problem there are m identical parallel machines in stage 1, while in stage 2 there is only one batch processor M and the objective is to minimize the maximum completion of all jobs, namely, the makespan ( C_max ). For the case of jobs' processing times in stage 1 are a_j = a ( j ∈ N = {1,2, …,n} ), we obtain an optimal solution in max{ O(n log n), O(nB) } time; for the case of the jobs' processing times in stage 2 are bj = b ( j ∈ N ), except for the case of b ≥ a_n ( a₁ ≤ a₂ ≤…≤a_n ) and B ≤ m ≤ n for which we obtain an optmial solution in O(n log n) time, for all the other cases and the general case (a_j(?) a, b_j (?) b ( j ∈N) ) we point out or prove their ( strongly ) NP - hardness, construct corresponding approximate algorithms and estimate their worst-case performance ratios ( cf. Table 1.1 ).In Chapter 3, we consider the flexiable two-stage flowshop scheduling problem. In this problem there are m dedicated parallel machines in stage 1, while in stage 2 there is only one batch processor M and the objective function is C_max. For the case of the jobs' processing times in stage 2 are b_ij = b ( i = 1,2, …, m; j = 1,2, …, n_i ), we obtain an optmial solution in polynomial time; while for the general case (a_ij(?) a, b_ij(?) b ( i = 1,2, …, m; j = 1,2,…, n(?) ) ) we give its strongly NP — hardness, construct corresponding approximate algorithm and estimate its worst-case performance ratio ( cf. Table 1.2 ).