Semi Online Scheduling Problems On Two Parallel Machines

Scheduling is one of the important branchs of operations research. Scheduling problem occurs in many applications such as load balancing network, communication channel assignment, parallel processing in large size computing, task assignment in flexible manufacturing systems, etc. Online scheduling is one of the focal problems investigated in scheduling at present. All information about the jobs is unknown to us in the actual online scheduling. According to the factual conditions, we ofen know the partial available information of the subsequent jobs. It admits the possibility of constructing a schedule with a better competitive ratio than online algorithms. We call such a problem semi online scheduling problem.In this thesis, we mainly study two semi-online scheduling problems on two parallel machines, and analyse competitive ratio of deterministic semi online algorithms. We consider three models and for each model we present a semi online algorithm. The thesis consists of three chapters.In Chapter 1, we give a brief introduction and basic knowledge for scheduling problems.In Chapter 2, we mainly consider two different semi online scheduling problems with non-simultaneous machine available time on two uniform machines. We suppose that the speed and available time of two machines are s₁ = 1, S₂ = s≥1, r₁ = r≥0, r₂ = 0, separately. One problem is semi online scheduling with the largest processing time being known in advance to maximize the minmum machine completion time. It is Q2, r₁|p_max|C_min by a three-field representation method. We give an MIN semi online algorithm with competitive ratio at least (s+1/(2s+1), and this bound is tight for the algorithm. The other is semi online scheduling with the total processing time being known beforehand, to minimize the maximum machine completion time, i.e., Q2,r₁|sum\C_min. We present an MH semi online algorithm with competitive ratio at most (2(s+1))/(2s+1).In Chapter 3, we consider a semi online scheduling problem on two identical parallel machines with a buffer, thereinto, the length of the buffer is k (it contains at most k jobs every time). The objective is to maximize the minimum machine completion time, namely, P2|buffer|C_min. We provide a semi online algorithm with competitive ratio at least (2/3).