Offline Versus Online Scheduling

If the scheduler chooses to discard J_i−1 and begins to execute Ji , the adversary then releases J_{i 1} at r_{i 1}. As long as the scheduler continues to discard the executing major job each time a new major job is released in order to execute the new job, the adversary continues to release the next major job ε units of time before the deadline of the executing job. This process continues until the major job J_max is released for some positive integer max, and the busy interval ends at the deadline of this job. In this case, the on-line scheduler discards all the jobs but J_max , and the total value achieved by the scheduler in this busy interval is emax . In contrast, the clairvoyant scheduler would schedule the jobs associated with all the major jobs before Jmax and then the major job Jmax and achieve the value
.

On the other hand, the scheduler may decide to complete Ji and, upon the completion of Ji , execute a job associated with J_{i 1} for i < max. In this case, the adversary stops releasing any major job after J_{i 1}. Moreover, it stops releasing jobs associated with J_{i 1} after the first associated job. (Figure 4–9 shows this situation for i = 2.) The value achieved in the busy interval by the on-line scheduler is approximately equal to ei . However, the clairvoyant scheduler would execute all jobs associated with jobs J0, J1, . . . , J_i−1 and then the job Ji and achieve a value of . Now suppose that the execution time e0 of the first major job J0 is 1, and for i > 0, the execution time ei of the ith major job is given by

If we perform the necessary algebraic manipulation, we will find that competitive factor of the on-line scheduler is either equal to 1/c, if the scheduler completes Ji followed by an associate job, or is equal to the ratio of emax to the sum
, if the scheduler discards all the major jobs except Jmax . The former is always greater than or equal to the latter for every positive integer max if c is equal to 4 or more. For c equal to 4,

the competitive factor is 0.25. The execution times of the major jobs are equal to 1, 3, 8, 20, 48, . . . . Figure 4–9 shows the case where the on-line scheduler executes J2 to completion. It achieves a value of 8 while a clairvoyant scheduler, knowing that all the jobs shown in the figure will be released at all time, can achieve a value of 32.