Research For Some Parallel Identical Shop Scheduling Problems

Parallel identical shop scheduling problems stem from cloud computing of big data,which is a hot topic in scheduling research in recent years.This thesis investigates parallel identical shop scheduling problems and mainly focuses on approximation scheme design and the worst-case ratio analysis.In the mparallel identical k -stage open-shops scheduling problem,the thesis considers the case of k =2 and any fixed constant k ?3 respectively.In the parallel identical two-stage flow-shops scheduling problem,the thesis considers the model of the number of the parallel identical flow-shop machine is a part of the input.This thesis is split into five chapters.In chapter 1,we first briefly introduce some basic concepts and related preliminary knowl-edge of scheduling problem,then we discuss some recent research results of parallel identical shop scheduling problems.In chapter 2,we mainly investigate m parallel identical two-stage open-shops scheduling problem.In this problem,every job has two open-shop operations,and it needs to be processed non-preemptively on any one of the open-shop without switches to the other open-shops.The objective is to minimize the finishing time of the last job.By using three-parameter,this problem can be denoted as P_m?O₂??C_max.We present a fully polynomial-time approximation scheme?FPTAS?for the problem.In chapter 3,we mainly investigate m parallel identical k stage open-shops scheduling problem.In this problem,every job has k open-shop operations,and it needs to be processed non-preemptively on any one of the open-shop without switches to the other open-shops.The objective is to minimize the finishing time of the last job.By using three-parameter,this problem can be denoted as P_m?O_k??C_max.We present a polynomial-time approximation scheme?PTAS?for the problem.In chapter 4,we mainly investigate m parallel identical two-stage flow-shops scheduling problem when mis a part of input.In this problem,every job has two flow-shop operations,and it needs to be processed non-preemptively on any one of the flow-shop without switches to the other flow-shops.The objective is to minimize the finishing time of the last job.By using three-parameter,this problem can be denoted as P?F₂??C_max.We present a polynomial-time approximation scheme?PTAS?for the problem.In chapter 5,we summarize our results and propose some directions for the further research.