On-line Scheduling With Precedence Contraints And Release Date

Scheduling is a very active branch of operations research,and it has an extensive and direct application foreground. Scheduling problems are a kind of important problems in the domain of combinatorial optimization. Moreover, on-line scheduling problems attract more attention of people because of its applications in practice.In generally, there are two different on-line models in on-line scheduling. They are on-line overlist and on-line overtime. In the former, jobs are ordered in some list and arrive one by one according to this list, and the current job needs to be irrevocably scheduled before the next job and all its characteristics become known. In the latter, jobs arrive over time, the characteristics of a job become known the job becomes known, which happens at its release dates. In both models, jobs must be irrevocably scheduled.This paper considers the on-line scheduling of identical parallel machines in which jobs arrive over time and with precedence constaints. The goal is to minimize the makespan. So in a sense, the scheduling model considered in this paper is the combination of the two on-line models described above( Evev if there are n jobs which arrived at the same time, their information is released one by one ). In section 1, we mainly introduce the background of scheduling and some related basic knowledge. In section 2, we study the on-line scheduling of identical parallel machines in which jobs arrive in the combined online scheduling of identical parallel machines in which jobs arrive in the combined on-line fashion. The goal is to minimize the makespan. We obtain that Greedy algorithm is optimal and the competitive ratio is 2—(1/m). In section 3, we consider two special cases of the above problem under the assumption that the jobs have the machine constraints. We prove that Greedy algorithm is also optimal for them, and the competitive ratios are O(log m) and m, respectively, where m is the number of machines.