On-line Scheduling On Batch Machines With Lookahead

Parallel batch scheduling is an important modern scheduling. In parallel batch scheduling, a machine can process b jobs simultaneously as a batch with capacity b. Jobs in a batch have a common starting time and a common completion time. The processing time of a batch is equal to the maximum processing time of jobs in the batch. In the LKβmodel, at a time instant t, an on-line algorithm can foresee the information of all jobs arriving in the time segment (t,t+β]. Incompatible job families means that jobs which belong to different families cannot be assigned to the same batch. In this paper, we consider four on-line batch scheduling problems of unit length jobs on parallel batch machine(s) with lookahead of the jobs arriving in a next time interval where the batch capacity is unbounded. The objective is to mininize the makespan. These problems are written as Pm|on-line, p-batch, b=∞,pj=1, LKβ|Cmax, 1|on-line, p-batch, b=∞,pj=1, LKβ,two families|Cmax, 1|on-line, p-batch, b=∞,pj=1,LKβ,families|Cmax, Pm|on-line, p-batch, b=∞:pj=1,LKp, f=m|Cmax, using the 3-field notation convention of Graham et al. (1979).In detail, we give the main results of this paper as follows.In Chapter 2, for the first on-line scheduling problem Pm|on-line, p-batch, b=∞, pj= 1, LKβ|Cmax, whenβ≥1/m, we present an optimal on-line algorithm H∞(β≥1/m). When 0<β<1/m, we first show that for any on-line algorithm of this problem, the lower bound of competitive ratio is 1+αm, where 0< am< 1 is a root of the equation (1+αm)(m+1)=αm+2-β∑i=1m(1+αm)i, then we provide a best possible on-line algorithm H∞(β<1/m) with a competitive ratio 1+αm. In Chapter 3,for the last three on-line scheduling problems with incompatible fami-lies,we prove that the lower bounds of these problems are at least 1+α2,1+αf,and 1+α, respectively,whereα2,αf,andαare positive roots of equations 2α22+(β+1)α2+β-2=0, f·αf2+(1+β)αf+β-f=0 andα2+(β+1)α+β-1=0,respectively.Then we provide,respectively, best possible on-line algorithms H2(β),Hf(β)and Hm(β).