| Online scheduling has become one of the fastest growing modern scheduling models in recent years.Comparing to the classical off-line scheduling,the obvious feature of online scheduling is that all jobs' information becomes known to the scheduler only by stages,and the scheduler have to take decisions depending only on the incomplete information of the instance as it is given so far.This feature not only brings the researchers a lot of difficulties,but also great interesting.There are many practical applications in manufacturing production and computer systems about online scheduling.In the literature, there are many versions about online.The most common are online-list scheduling and online-time scheduling.In the online-list scheduling problem,the jobs are ordered in some list and presented one by one according to the list.Every job must be assigned to some machine before the next job appears.When the job is released,the scheduler knows all its information.In the online-time scheduling problem,the jobs arrive over time.A job's information becomes to known until it arrives.The job do not have to be scheduled immediately upon its arrival.In this thesis,we consider the latter,i.e.,online-time scheduling.The quality of an online algorithm is usually measured by its competitive ratio.We say that an online algorithm isÏ-competitive if,for any instance,it produces an objective value at mostÏtimes the objective value given by an off-line optimal schedule.Given an online scheduling problem P,we say an algorithm A is a best possible online algorithm for problem P if,there exists no online algorithm has a better competitive ratio than that of algorithm A.Batch scheduling has also been one of extensively studied modern scheduling models in the last two decades.It contains serial-batch scheduling and parallel-batch scheduling. In the former model,jobs form a batch when they share the same setup time on a machine, and the machine can process a job at a time.The processing time of a batch is equal to the setup time plus the sum of processing times of all jobs in the batch.In the latter model,the machine can process several jobs simultaneously as long as the batch capacity is not exceeded.The processing time of a batch is determined by the largest processing time of all jobs in the batch,and all jobs in a batch have the same starting time and the same completion time.In the literature,there are two versions about parallel-batch scheduling:One is unbounded model,i.e.,b=∞;the other one is bounded model,i.e., b＜n,where b is the capacity of batch.In this thesis,we consider the parallel-batch scheduling with b=∞.There are two kinds of scheduling problems studied in this thesis.In Chapter 2 and Chapter 3,we consider online scheduling on parallel-batch machines to minimizing makespan.In the latter chapter,the jobs are from different incompatible families.From Chapter 4 to Chapter 6,we study online scheduling with delivery times.In these models, once the job is completed on the machine,we use a vehicle delivering it to its destination. The objective is to minimize the time by which all the jobs have been delivered,i.e.,the sum of the last job's completion time and its delivery time.In Chapter 4,we study online scheduling on a single machine with restricted delivery times.In the last two chapters, we consider online scheduling on a single parallel-batch machine with restricted delivery times in Chapter 5,and unrestricted model in Chapter 6.In detail,the main results are as follows:1.In Chapter 2,we consider online scheduling on m parallel-batch machines to minimize the makespan where the batch capacity is unbounded.We give a lower bound 1+αm on the competitive ratio,whereαm is the positive solution of the equationαm2+ mαm-1=0,and establish a best possible online algorithm matching this lower bound. Simultaneously,we also provide a lower bound 3/2 on the competitive ratio for densealgorithms, and present a best possible dense-algorithm matching this lower bound.2.In Chapter 3,we consider online scheduling on m parallel-batch machines in which the batch capacity is unbounded and all jobs belong to m incompatible job families. The incompatible job family means that jobs from different families cannot be processed together in the same batch.The objective is to minimize makespan.We give a lower bound(51/2+1)/2 on the competitive ratio,and provide an online algorithm Hm(θ), whereθ∈(0,1) is a parameter.Under the condition that jobs belonging to the same family have identical processing times or m=2,we show that Hm(α) is a best possible online algorithm,whereα=(51/2-1)/2.For the situation m≥3,we prove that Hm(β) has a competitive ratio no more than(3+β)/2=(2+21/2)/2,whereβ=21/2-1,and show that no matter what the value ofθis,the competitive ratio of algorithm Hm(θ) is no less than 1+101/10/5. 3.In Chapter 4,we consider the on-line version of the single machine with delivery times of jobs.The objective is to minimize the time by which all jobs have been delivered. We assume that a job's processing time is no smaller than its delivery time.We show that any on-line algorithm has a competitive ratio of at least 21/2,and provide a best possible online algorithm matching this lower bound.4.In Chapter 5,we consider the on-line version of the single machine unbounded parallel-batching scheduling with delivery times of jobs.The objective is to minimize the time by which all jobs have been delivered.We assume that a job's delivery time is no smaller than its processing time.We show that any on-line algorithm has a competitive ratio of at least(31/3+1)/2,and provide an on-line algorithm with a competitive ratio 51/2+1)/2.5.In Chapter 6,we study the online single parallel batch machine scheduling problem with delivery times where the batch capacity is unbounded.The objective is to minimize the time by which all jobs are delivered.We provide an online algorithm with a competitive ratio 221/2-1.
|
PDF Full Text Request