Online Scheduling Of Parallel Jobs On Identical Machines

Scheduling theory has been one of the most active and extensive used research topics in the world. Scheduling problem is to complete the tasks optimally by using the given resources and under the constraint conditions. In general, a scheduling problem contain jobs that should be processed, i.e. tasks that should be executed and machines that offer the service, i.e. resources needed to complete the tasks. A schedule is for each job an allocation of one or more time intervals to one or more machines. The goal is to make one or more objective functions to be maximal or minimal.In this paper, we study online scheduling of parallel jobs on identical machines. There are m identical machines and a job set including n independent parallel jobs Ji,J2,J2,…,Jn.Every job Jj (j= 1,2,…,n) has a positive integer processing time Pj, which is also called the length of job Jj. The width mj of job Jj is the number of simultaneously required machines when it is processed, where 1< mj< m. Online scheduling means that jobs may arrive one by one or over time. If jobs arrive online, all their characters can not be known until their arrival times. Parallel job may require more than one machine for its processing at a time. And it should be processed with the same start time and the same completion time on the machines that it used. There are two differernt types of parallel jobs according to their widths:malleable parallel jobs and nonmalleable parallel jobs. Malleable parallel jobs can change their widths according to the need, while the width of nonmalleable parallel jobs are fixed. On the other hand, jobs may be interrupted or not when it is processing. Jobs are preemptable if the execution of any job can be suspended and restarted later without additional costs. Otherwise, we call them nonpreemtive jobs. In our research, we only consider the optimality criteria of schedule length (makespan).In Chapter 2, we investigate online scheduling of malleable parallel jobs on identical machines, where jobs are independent and arrive over time. Here pre-emption is not allowed. The execution time of job Jj processed on kj machines is defined as tj= pj/kj+(kj-1)cj, where cj (cj＞0) is an exclusive setup time of job Jj. We present an online algorithm with competitive ratio 1+a for the case of two identical machines, where a= ((?)5-1)/2 is the positive solution of equation a2+a = 1. Furthermore, we show that there is no online algorithm with competitive ratio smaller than 1+a on the case of m (m≥2) identical machines. So our online algorithm is optimal for the case of two machines.In Chapter 3, we investigate online scheduling of nonmalleable parallel jobs on identical machines, where jobs arrive over time and preemption is allowed. Every job Jj has a nonnegative integer arrival time aj, a positive integer length pj and a positive integer width mj (1< mj≤m). For the case of scheduling on two identical machines and the case of scheduling only two types of jobs (mj = 1 or m) on m identical machines, where it is assumed that the number of simultaneously required machines is improtant, we present optimal online algorithms with competitive ratio 1 by using "temporary schedule". We also consider the model that the fixed set of simultaneously required machines is assumed to be important. For the case of scheduling on two indentical machines, we present an optimal online algorithm with competitive ratio 1. For the case of scheduling on three indentical machines, we prove that there is no online algorithm with competitive ratio smaller than 5/4.In Chapter 4, we investigate online scheduling of nonmalleable parallel jobs on identical machines with time windows. The problem can be studied in two different ways according to the beginnings of time windows are known or not. We consider two online models:jobs arrive one by one and jobs arrive over time. Here preemption is allowed. For the case of scheduling on two identical machines and jobs arrive one by one, we prove that there is no online algorithm with constant competitive ratio. For the case of scheduling on two identical machines and jobs arrive over time, where the fixed set of simultaneously required machines is assumed to be important, we present an optimal online algorithm with competitive ratio 1. Besides these, for the case of scheduling on two identical machines and jobs arrive over time, where the number of simultaneously required machines is assumed to be important, we present an optimal online algorithm with competitive ratio 1 when the beginnings of time windows are known and we present an approximatly optimal online algorithm with competitive ratio 1+∈/2+∈(∈→0) when the beginnings of time windows are not known.