On-line Batching Scheduling Considering The Objective With Weight And Delivery Time

Scheduling theory,as an important research direction of the Operations Research,is one of the hottest areas in the Operations Research discipline.This is also an important part of combinatorial optimization theory.Where,a large number of different machine environments and jobs' characteristics and the scheduling models produced by the differ-ent objective functions,widely studied by scholars at home and abroad,which got rich theoretical results.For the different scheduling models,by the nature of the jobs that can be divided into off-line scheduling and online scheduling.In the off-line scheduling models,the information of all jobs is known before the scheduling.While in the online scheduling models,all information about jobs is known only after they are reached.So in the online scheduling models,decision makers can only make decisions based on information that has already arrived at the current jobs.The LK? model of online scheduling means that the Lookahead model.Online algorithms at arbitrary decision time t can predict information of all jobs in advance at the time interval(t,t+?]to make more reasonable decisions for decision makers.For different batch-scheduling models,according to the method of the batch it can be divided into parallel-batch scheduling and serial-batch scheduling.In the parallel-batch scheduling models,a machine could process several jobs as a batch at the same time.The processing time of the batch equals the longest processing time of the all jobs in this batch,and all jobs in the batch have the same starting time and completion time.In the serial-batch scheduling models,a machine could process several jobs as a batch sequentially.The processing time of the batch equals the total processing time of the all jobs in this batch.The completion time of this batch equals the completion time of the last job in the batch.Also,the scheduling models can be divided into batch capacity bounded case and batch capacity unbounded case according to the capacity of a batch,where the capacity of a batch refers to the number of jobs that can be processed in one batch.Jobs equip with delivery time in the online scheduling models,which means that the job can be transported to its destination by transportation facilities after it is finished the processing.Then we can consider the objective function which is to minimize the maximum delivery completion time.Jobs equip with weights time in the scheduling models,which refers to assign the job a certain weight,considering unit time consumption of this job,to minimize the total consumption in its completion time.Then we can consider the objective function which is to minimize the maximum weighted completion time.In this thesis,we research some batch models of online scheduling problems about several different processing machines with batch disposes.The models studied are repre-sented by the scheduling three-field notation:The description of the first model:In this model,what we are researching is the online bounded parallel-batch with delivery time and lookahead at a single machine.The objective function is to minimize the maximum delivery completion time.In this model,we assume jobs have the same processing time pj = 1,and consider batch capacity bounded case.We give a lower bound of this model,and provide an online algorithm for this model.Then we prove that when O ???1/6,the competitive ratio of the online algorithm is 1+?,which is the best possible online algorithm,where ?is a positive root of the equation ?2 +(? + 1)? + ?-1 = 0;When ?>1/6,the competitive ratio of this online algorithm is 3/2.The description of the second model:In this model,what we are researching is a multiple-machine batch of online unbound-ed scheduling problem with the weight of the job,the objective function is to minimize the maximum weighted completion time.In this model,all jobs arrive over-time,each job Jj has an arrival time rj,and we assume that each job has the same processing time pj=1.Jobs are processed within batches,the number of the processed jobs in a batch is unlimited.That is,the batch capacity is unbounded.We give a lower bound of this model,and provide an online algorithm that makes the competitive ratio of the online algorithm to match with the lower bound of this model.Then we prove that the online algorithm is the best possible online algorithm.The description of the third model:In this model,what we are researching is the batch of online bounded scheduling problem with jobs' weight and lookahead at a single machine,the objective function is to(1)l|online,p-batch,pj = 1,qj,6<?,LK?,Lmax.(2)Pm|Online,p-batch,pj = 1,b=?| max{wjCj}.(3)1{online,p-batch,pj = 1,b<?,anti-agreeable(rj,wi),LK?|max{wjCj}.minimize the maximum weighted completion time.In this model,all jobs arrive over-time,each job Jj has an arrival time rj.we assume that each job has the same processing time Pj=1,and the weight of each job is recorded as wj.Jobs are processed within batches,the number of the processed jobs in a batch is limited.That is,the batch capacity is bounded.In this model,we consider a special case,which makes the weight of the job to be anti-agreeable with the arrival time of the job.In other words,for any two jobs Ji and Jj,when there is satisfied ri<rj,it implies wi?wj.We prove that there is no competitive ratio of online algorithms for this model is less than 1 + ?,where ? is a positive root of the equation ?2 +(? + 1)? + ?-1 = 0(0???1).Finally,we provide an online algorithm Hb(?*,?),and prove that when 0 ??? 1/6,the competitive ratio of the algorithm is matched with the lower bound of the given model.Then we prove that when 0 ??? 1/6,the online algorithm is the best possible online algorithm;And when?>1/6,we prove that the competitive ratio of the algorithm is 3/2.