Semi Online Uniform Machine Scheduling And Related Problems

Scheduling is to assign jobs processed on machines under some constraints such that one or multi-criteria attain to the optimum. It can be divided into classical scheduling and modern scheduling. Compared with the classical scheduling, the modern scheduling is nonclassical and new-type. There have been more than ten modern scheduling models which are widely discussed over the last twenty years, such as the scheduling with controllable processing time, the batching scheduling, multi-criteria scheduling, on line scheduling, semi-on-line scheduling and so on.In chapter 1, some notation, definitions and basic background information about the subject are introduced.In chapter 2, we consider the semi-on-line scheduling problems on uniform machines, where the largest processing time of all jobs is known in advance. The objective is to minimize the maximum machine completion time. If there are three uniform special machines and the speed of machines are given by S₁ = S₃ = s≥1 = S₂, we provide an algorithm whose competitive ratio is not greater than (4s+2)/3s (1 < s≤2) and (3s+1)/2s (s > 2).In chapter 3, we consider the semi-on-line two uniform machines scheduling problems, where the objective is to minimize the maximum job completion time. For the semi-online with known total processing time and largest processing time, an optimal semi-on-line algorithm with competitive vatio (4s+2)/(3s+2) is presented.