A Class Of On-line Batch Scheduling Problems On Parallel Machines

Due to its profound significance in both real world and theory, scheduling has always been an important branch in the research of combinatorial optimization. In this dissertation, we mainly considered a class of on-line batch scheduling problems on parallel machines, where the objective functions are minimizing total weighted job completion time, and presented some approximation algorithms. Four chapters are included in the dissertation.In Chapter 1, we briefly introduced some definitions, notations and basic information about scheduling.In Chapter 2, we considered the problems of on-line batch scheduling on identical machines and unrelated machines, where the objective functions are minimizing total weighted job completion time. By using of the "Greedy Interval", we investigated the problem of on-line batch scheduling on identical machines, and presented an on-line algorithm with competitive ratio no more than 8;We also provided an on-line 16-competitive algorithm for the problem of batch scheduling on unrelated machines.In Chapter 3, we considered two scheduling problems on uniform machines, we designed an on-line (4 + ε)-competitive algorithm for the scheduling problem on uniform machines;For the batch scheduling problem on uniform machines, we obtained an on-line algorithm with competitive ratio no more than 8.In Chapter 4, we summarized the dissertation and put forward some problems which we will consider further.