Line Parallel Machine Scheduling Problem

Scheduling is one of the active branches in combinatorial optimization problems which has received great attention in decades. This thesis concentrates on some on-line scheduling problems on parallel machines which consists of six chapters. We introduce preliminary concepts related to approximation algorithms and complexity theory in Chapter 1.In Chapter 2, we investigate the on-line scheduling problem of unit jobs on m identical parallel machines. The goal is to maximize the number of jobs completed on time. We give a lower bound of the problem, and present a simple LS algorithm with competitive ratio of 2. A best possible on-line algorithm MEDF, which has the property of "immediate notification", is given for the two-machine case.In Chapter 3, we go on considering the on-line scheduling problem of unit jobs on m identical parallel machines. For the sake of convenience, we let all the jobs have an equal length p, and all parameters associated with a job are integers. We give an improved on-line algorithm with competitive ratio of 1/(1 - (m/(m + 1))~m), which tends to e/(e-1)≈1.582. Moreover the algorithm satisfies the property of "immediate decision". In addition, some lower bounds are given for the on-line algorithm with the restriction.In Chapter 4, we study the problem of on-line scheduling jobs on m identical parallel machines in the Preemption-restart model, in which jobs can be preempted, but preempting results in the work done on this job so far being lost. The objective is to maximize the number of jobs completed on time. We first show a lower bound of 4/3 for the problem, and then give an on-line algorithm with competitive ratio of 2.In Chapter 5, we discuss the problem of on-line scheduling a set of jobs with arbitrary release times on m identical parallel machines. The goal is to minimize the makespan. In this problem, jobs appear in an order. We do not know the existence of other new jobs until the current job is given a processing slot. In this on-line situation, the sequence of jobs' release time is arbitrary, not as in the classical model in which the sequence of jobs' release time is non-decreasing. A best possible on-line algorithm is given for the two-machine case. For the special case that all the jobs have unit processing time, we show algorithm LS has a tight bound of 3/2. Finally, In Chapter 6 we present a summary of our results, and point out some future work along this direction.