Online Parallel-batch Scheduling To Minimize The Maximum Weighted Completion Time

In off-line schedule, all information of jobs is released before the beginning of schedul-ing. In this paper, we discuss online over time scheduling problems. It means that the information of the jobs is not known in advance, but released one by one over time.In this paper, we study the problems of online parallel-batch scheduling. Parallel-batch scheduling is an important problem of scheduling research. There are m machines in the parallel machine scheduling. A batch machine can handle up to b jobs simultaneously as a batch. The processing time of a batch is defined to be the maximum processing time of jobs in the batch. According to the capacity of batch, there are two versions of parallel-batch scheduling:the bounded model and the unbounded model.In the second chapter we consider online scheduling on one machine. The objective is to minimize the maximum weighted completion time of jobs. We provide a best possible online algorithm of competitive ratio 2 when the batch capacity is 1.In the third chapter we consider online scheduling of unit length jobs on parallel-batch machines. The objective is to minimize the maximum weighted completion time of jobs. When the batch capacity is bounded, using the 3-parameter notation, the problem we study in this paper can be denoted as:Pm|online,p-batch,b<∞,pj=1|WCmax. We provide a best possible online algorithm of competitive ratio (?)+1≈1.618. We also provide a new lower bound 2 on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound. When the batch capacity is unbounded, we provide a best possible dense-algorithm of competitive ratio (?) for problems Pm|online,p-batch,prec, b=∞,pj=1|WCmax and Pm|online,p-batch,prec, b= ∞, pj=1|∑wjcj. This conclusion remains valid when jobs are independent.In the fourth chapter we consider the online scheduling of incompatible job fami-lies on unbounded parallel-batch machines with lookahead. The jobs have the unit-length and same weight. In the lookahead model, at a time instant t, an online algorithm can foresee the information of all jobs arriving in the time segment (t,t+β]. By incompat-ible job families, we mean that jobs from different families cannot be assigned togeth-er in the same batch. When the jobs have the same weight, the maximum weighted completion time was converted into the makespan. For problem Pm|online,p-batch, b= ∞, pj=1,LKβ, f-families,β≥[f/m]|Cmax, we give a optimal online algorithm. For problem Pm|online, p-batch, b=∞,Pj=1, LKβk, f-families, f=km,βk∈[k-1, k)|Cmax, we give a best possible online algorithm of competitive ratio 1+αk,where αk is the positive root of the equationκακ2+ακ(βκ+1)+βκ-κ=0.For the general case,we also provide a new lower bound on the competitive ratio for dense-algorithms,and present a best possible dense-algorithm matching this lower bound.