On-line Scheduling With Lookahead And Delivery Times

Scheduling is to assign some tasks to time resources under some constrains, such that one-and multi-criteria attain to the optimum. Recently, parallel batch scheduling and on-line scheduling are two flourishing scheduling models. In the parallel batch scheduling model, a machine can process several jobs simultaneously as a batch, and the processing time of the 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. In the on-line scheduling model, all job informations are unknow before their release times, and once a job is scheduled it cannot be changed. In the LKβ model, an on-line algorithm can foresee the information of all jobs arriving in the time segment (t,t+βp(t)], which p(t) is the longest processing time of the available jobs at a time instant t.In this paper, we consider two kinds of scheduling models:(1) on-line scheduling with lookahead on parallel batch machine.(2) on-line scheduling with delivery times on a single machine.These problems are written as1|on-line, rj, p-batch, b=∞, LKβ|Cmax;1|on-line, rj, p-batch, agreeable(pj, qj), b=∞,LKβ|Lmax;1|on-line, rj, qj≥pj|Lmax.using the3-field notation convention of Graham et al.In detail, we give the main results of this paper as follows.In Chapter2, for the first two on-line scheduling problems on parallel batch mach-ine, we prove that the lower bounds of these problems are at least1+α, where α is a root of the equation α2+(β+1)α+β-1=0, then we respectively provide on-line algorithms H1(α,β) and H2(α,β) with a competitive ratio1+α. Then we prove that H1(α,β) and H2(α,β) are the best possible on-line algorithms when0<β≤1/6. In Chapter3, for the last on-line scheduling problem1|on-line,rj,qj≥Pj|Lmax, we first show that for any on-line algorithm of this problem, the lower bound of competitive ratio is (?), then we provide an on-line algorithm H with a competitive ratio (?).