Approximation Algorithms For Two-machine Open Shop Scheduling Problems With A Single Server

In this thesis, we consider two-machine open shop scheduling problems with a single server, which is the generalization of classical open shop scheduling problems. In the problems each operation of all the jobs must be set up on a machine by a single server before it is processed by the machine.In this paper we study four problems, all of which have the same objection to minimize the maximum completion time. According to the different constraints, we give four approximation algorithms for each of them and prove the worst-case performance ratios. The main results are as follows:(1) For the problem O2, S1│Sij+Pij=a│Cmax, in which all the jobs'length are equal, we give the approximation algorithm L and show its worst-case performance ratio is 3/2.(2) For the problem 02,S1│Pij=p│Cmax, in which all the jobs'processing time are equal, we give the approximation algorithm F and show that its worst-case performance ratio is not more than3/2.(3) For the problem O2,S1│max{Sij}≤min{Pij}│Cmax, in which the largest server time is not more than the smallest processing time, we give the approximation algorithm SST and show its worst-case performance ratio is3/2.(4) For the problem 02,S1│max{Pij}≤min{Sij}│Cmax, in which the largest processing time is not more than the smallest server time, we give an optimal algorithm.