On-line 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 immediately after its arrival or if its processing is aborted, the job is lost. The goal is to maximize the total value of all processed jobs. In general, this problem does not allow on-line approximations with finite worst case guarantee. We give an approximation algorithm with worst case ratio four for large classes of special instances, and we also prove that the factor four is best possible. One of our classes contains the instances where the job values are proportional to the job lengths.