ONLINE SCHEDULING OF JOBS WITH FIXED START AND END TIMES

We investigate an on-line scheduling problem on a single machine where jobs have fixed start and end times. If a job is not processed immedi ately after its arrival or if its processing is aborted, the job is lo st. The goal is to maximize the total value of all processed jobs. In general, this problem does not allow on-line approximations with finit e worst case guarantee. We give an approximation algorithm with worst case ratio four for large classes of special instances, and we also pr ove that the factor four is best possible. One of our classes contains the instances where the job values are proportional to the job length s.