Semi On-line Scheduling Problems On Two Uniform Machines With Machine Available Times

In this thesis, two semi on-line scheduling problems on two uniform machines with non-simultaneous machine available times are considered.The thesis is organized as follows.Chapter 1 gives a brief introduction of the parallel machine scheduling problems, including basic knowledge about scheduling , semi on-line scheduling , scheduling problems with non-simultaneous machine available times and the scheduling problems on two uniform machines. Chapter 2 deals with the first semi on-line scheduling problems on two uniform parallel machines with non-simultaneous machine available times, where the total processing time is known in advance, to minimize the maximum machine completion time and to minimize the maximum job completion time. We give approximation algorithmswith a competitive ratio of (?)2 , while there is no approximation algorithm with a competitive ratio of smaller than (1 + (?)3)/2. Chapter 3 deals with the second semi on-line scheduling problems on two uniform machines with non-simultaneous machine available times, where the largest processing time is known in advance, to minimize the maximum machine completion time and to minimize the maximum job completion time. We give approximation algorithms with a competitive ratio of 3/2, while there is no approximation algorithm with a competitive ratio of smaller than (?)2 . It can be concluded that about two semi on-line scheduling problems on two uniform machines where the total processing time is known and the largest processing time is known in advance, respectively, it is not effect on their competitive ratio whether non-simultaneous machine available times exist or not.