Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs

Motivated by issues raised from data broadcast and networks using ATM and TCP/IP, we consider an online scheduling problem on a single machine. In the problem, each job i is revealed at release time r i , has processing time p i , deadline d i and weight w i . Preemption is allowed and there are two models of preemption: preemption with restart and preemption with resume. The goal is to maximize the throughput — the total weight of all jobs completed on time. In the paper, we consider the problem where all processing time of jobs are equal and present improved algorithms which achieve 4.24-competitive in both models of preemption