Similar Parallel Machine Scheduling Problem

In this thesis, two semi-online scheduling problems with combination of two types of information are considered. One is scheduling on two identical machines with non-simultaneous available time, the other is scheduling on two uniform machines . The thesis is organized as follows.Chapter 1 gives an introduction of the parallel machine scheduling problems, basic knowledge about scheduling and semi-online scheduling with single information. Chapter 2 mainly deals with the semi-online problem on two identical machines with non-simultaneous available time, where the total processing time and the largest processing time are known in advance, to minimize the maximum machine completion time. We give an optimal algorithm SM with competitive ratio of 6/5. Chapter 3 chiefly considers the other semi-online problem on two uniform machines, for which the total processing time and the largest processing time are known in advance, to maximize the minimum machine completion time. We present the approximation algorithm SD while prove its competitive ratio is (3s+2)/(2s+2).