Online scheduling with hard deadlines
In this talk, we deal with the following online scheduling problem. We are given m identical machines. All jobs have identical processing times. Each job is associated with a release time and a deadline, neither of which is known until the job appears. As soon as a job is available, we must immediately decide if the job is accepted or rejected. If a job is accepted, it must be completed by its deadline. The goal is to maximize the total number of jobs accepted. We study various strategies for designing an on-line algorithm. Our main result is deriving a nontrivial on-line algorithm with competitive ratio 3/2 for the two-machine case, which is best possible. Deterministic lower bounds and a greedy algorithm for the general case are also given.