A Study Of Some Two-stage Shop Scheduling Problems

This thesis, we mainly investigate two kinds of the two-stage scheduling problems: one is the open shop scheduling problem in two-stage, the other one is the hybrid shop scheduling problem in two-stage. Proving the computational complexity of the problem are one of the focus of the research,which also includes to design the approximation algorithm for the problem, and prove the worst case bound of the algorithm. Our thesis contains four chapters.Specific contents are as follows:In chapter 1, we introduce some basic concepts and theories of the scheduling problem.In chapter 2, we mainly consider a new type open shop scheduling problem with two-stage inside. That is an open shop at the first stage followed by a flow shop at the second stage.The goal is minimizing the makespan. The requirement is that once a job is processed in a flow shop, it can be released only when it has finished flow shop processing tasks. Dividing the problem into two cases, the goals of the two cases are both minimizing the makespan.The first one is m parallel machines at the first stage followed by two machines at the second stage. We provide an approximation algorithm for the problem with the worst-case ratio of2. The second is only one machine at the first stage followed by two machines at the second stage. We firstly prove the computational complexity of the problem, that the problem is NP-hard. Then we also provide an approximation algorithm for the problem with the worst-case ratio of5/3 and give a prove of the worst case bound.In chapter 3, we study the two-stage hybrid shop scheduling problem. The first stage is an open shop with two machines and the second stage is a flow shop model including two machines. The requirement is that a job can choose any unprocessed machine to process,and the goal is to minimize the makespan. Similarly we prove that the problem is NP-hard.An approximation is provided and the worst-case ratio is27/14.In chapter 4, we summarize our results and list some remarking conclusions for the future study.