Two Models On Batch Scheduling Of Weighted Sum Objectives

Recently,parallel batch scheduling and on-line scheduling are two flourishing scheduling models.Parallel batch scheduling means that a machine can process several jobs(unbounded or bounded) simultaneously as a batch.All jobs in a batch start and complete at the same time,respectively.The processing time of a batch is equal to the longest processing time of the jobs assigned to it.Once a batch is started,it cannot be stopped until its completion.On-line scheduling means that all jobs' informations are unknown before their release times,and once a job is scheduled it cannot be changed.In this paper,we mainly consider two kinds of models with weighted sum objectives on batch scheduling.First of all,we investigate an on-line model:on-line schduling on a single batching machine in which the objective is to minimize the weighted sum of square completion time.Here,we have a batching machine.There are n jobs 1,2,…,n which arrive on-line over time.Each of them has a processing time p_j,a weight w_j and a arrival time r_j.The batch capacity b is either unbounded or bounded.Thus the two models under research can be denoted by 1|on-line,r_j,p-batch|∑w_jC_j~2 and 1|on-line,r_j,p-batch,b＜n|∑w_jC_j~2,respectively.The main results on this research are as follows.(1) We give an on-line algorithm with competitive ratio 16+O(ε)((?)ε)＞0) for the model 1|on-line,r_j,p-batch,b＜n|∑w_jC_j~2.(2) We give an on-line algorithm with competitive ratio 11.3429 for the model 1|on-line, r_j,p-batch|∑w_jC_j~2.Then,we discuss an off-line model:the single machine parallel batch scheduling in which the objective is to minimize the weighted sum of constant powered completion time. Here,we just consider the model with unbounded batch capacity.This problem is denoted by 1|p-batch,r_j|∑w_jC_j~h(h≥1 is a constant).We use the methods of partition the time horizon and geometric rounding and translate the original instances to simplier instances. Further,with the known pseudopolynomial algorithm we give a fully polynomial-time approximation scheme for the model 1|p-batch,r_j|∑w_jC_j~h(h≥1 is a constant).