Research On Parallel Multi-Stage Shop Scheduling Problem

In the thesis.the parallel multi-stage shop scheduling problems,including the parallel flowshop scheduling problem(PFS)and the parallel openshop scheduling problem(POS):are discussed from the perspective of approximation algorithm.These problems have a wide range of applications,including glass manufacturing,logistics scheduling,cloud computing,and so on.The thesis consists of five chapters.In Chapter 1,we give an introduction to the scheduling problems and the parallel flowshop(openshop)scheduling problem.and give some the basic concepts and definitions used throughout this thesis.In Chapter 2,we discuss the problem of scheduling n k-stage jobs on m parallel flowshops,denoted as(m,k)-PFS.For the general problem,we give a ?k-approximation algorithm,where p represents the ratio of the algorithm used to solve the parallel machine scheduling problem.Furthermore,we study(m,2)-PFS and obtain an approximation algorithm with ratio max{1,?}(1-?)+?/1+?,where ? is the maximum value(over all jobs)of the processing time ratio of the first operation to the second operation and ? is an arbitrary positive number.Finally,for a special case of(m,2)-PFS problem,we obtain an approximation algorithm with ratio 3/1+?.In Chapter 3.we discuss(m,3)-PFS,where m is an arbitrary number,and propose a(23/6-1/3m)-approximation algorithm.In Chapter 4,we study the problem of scheduling n three-stage jobs on m three-stage openshops,named(m,3)-POS.For the general problem,where m,is an arbitrary number,we present an approximation algorithm with ratio 3?.In Chapter 5,we summarize our results and point out some further research directions on the parallel shop scheduling problems.