Online Scheduling On Parallel Machines With Kind Release Times

Scheduling is an important optimization problem in Operational Research.Its definition can be described as follows.We allocate time slots on the machine to the jobs to make one or more objectives optimal under some resource constraints.Scheduling has been widely used in various fields such as industrial manufacturing,computer science,logistics and transportation management,and has important theoretical research value and broad application prospects.This thesis focuses on the online scheduling on parallel machines under the KRT environment.The online scheduling in this thesis refers to over-time online scheduling,which means that each job has a release time,and all information about the job is known only when it arrives.The scheduler has no information about the future jobs and can only make decisions based on known jobs information,and no changes are allowed once the decision is made.The KRT assumption is a constraint on the release time of jobs,which means that no jobs are allowed to arrive when all machines are busy,in other words,jobs can only arrive when at least one machine is idle.Parallel machines means that the machines are identical in function and speed and that only one job can be processed on each machine at the same time.The information of any job Jj are release time rj,processing time pj and delivery time qj.The completion time of Jj on the machine is denoted by Cj.Once Jj is finished at the machine,it needs to be immediately delivered to a destination by vehicle(assuming a sufficiently large number of vehicles),which also costs delivery time qj.Denote by Lj the time by which job Jj is delivered to the destination.The objective is to minimize the time by which all jobs have been delivered,i.e.,Lmax=max{Lj,1 ≤j ≤n}.In chapter 1 we introduce the research background,the basics knowledge,the reviews of research and the structure of the thesis.In chapter 2,firstly,we study the online scheduling problem P2|online,rj,KRT,qj|Lmax,prove that there is no online algorithm with competitive ratio less than(?)for this problem,and prove the competitive ratio of online LDT algorithm is 3/2.Then,a best possible online algorithm with a competitive ratio of(?)is designed for a special case pj=p.In chapter 3 we focuse on the online scheduling problem on a parallel machine with equal-length jobs without KRT assumption Pm|online,rj,pj=p,qj|Lmax.Firstly,we prove that there is no online algorithm with competition ratio less than((?)+5)/6 for this problem.Then,a best possible online algorithm matching the lower bound is designed for the case m=2.Finally,comparing the results of this problem under KRT environment in Chapter 2,we find that the KRT assumption reduces the competitive ratio of the best possible online algorithm for this problem from((?)+5)/6 to(?).In chapter 4 summarizes the results of this dissertation...