Design And Analysis Of Approximation Schemes For Some Two-stage Scheduling Problems

Scheduling problem is a young branch with important significance in combinatorial optimization problems.This thesis mainly analyzes and studies three scheduling problems in two-stage hybrid workshops,and gives polynomial time approximation scheme of each problem.Because these problems are widely presented in the manufacturing of machinery,the research on such problems has important practical significance.This thesis is divided into five chapters.In chapter 1,we first introduces the professional terms and related concepts related to scheduling problems,and then gives the concepts related to algorithm design and analysis,such as approximate algorithms and polynomial time approximation schemes.Finally,it describes the models and research status of hybrid workshop scheduling problems which are related to this thesis.In chapter 2,we mainly investigate scheduling problem of two-stage hybrid flow shop.In this problem,every job has three operations,and the third operation is required to start processing if and only if the first and second operations are completed.That is to say,the machine environment consists of two stages,the first stage consists of two open shop machines,the second stage consists of one machine,and the processing of jobs between the two stages must conform to the flow shop.We present a polynomial-time approximation scheme( )for this problem.In chapter 3,we mainly investigate scheduling problem of two-stage hybrid open shop.In this problem,every job has three operations,and the second operation is required to start processing if and only if the first operation is completed,and the third operation of the job can be processed on any of parallel machines.That is to say,the machine environment consists of two stages,the first stage consists of two flow shop machines,the second stage consists of m parallel machines,and the processing of jobs between the two stages must conform to the flow shop.We present a polynomial-time approximation scheme( )for the problem.In chapter 4,we mainly investigate scheduling problem of two-stage hybrid shop.In this problem,every job has three operations,and the second operation is required to start processing if and only if the first operation is completed.It is necessary to pay attention to the difference of the machine environment between this problem and the scheduling problem in Chapter 3:In Chapter 3,the third operation of each job is required to start processing after the completion of the second operation or before the start of the first operation.In this chapter the third operation of each job can be processed at any time that does not conflict with other processes.We present a polynomial-time approximation scheme( )for this problem.In chapter 5,we summarize our results and propose some directions for the further research.