Revisiting Real-Time Interval and Throughput Maximization
For scheduling theorists, the paper clarifies the boundaries between interval scheduling and general real-time throughput, providing both positive and negative results that refine understanding of competitive ratios under different models.
The paper revisits real-time interval scheduling and throughput maximization, showing that constant competitive algorithms exist for unweighted and proportionally weighted throughput with preemption and restarting, and that advance notice enables constant competitive ratio without preemption for proportionally weighted jobs, but not for arbitrary weight functions. It also proves that unweighted throughput with preemption and revoking has no constant competitive ratio when processing times are unrestricted.
Job throughput maximization is the central maximization problem in scheduling. Interval scheduling is the special case of throughput maximization when jobs are intervals and therefore there is no slack available in which to schedule a job. It is interesting to know to what extent results for interval scheduling can be extended to the more general throughput problem in the real-time model. For the unweighted and proportionally weighted throughput problem (where the weight or value $w_i$ of a job $J_i$ is its processing time $p_i$), there are constant competitive real-time scheduling algorithms using preemption with restarting. More generally, the result for proportionally weighted interval scheduling can be extended to C-Benevolent weight functions. We also introduce a new real-time model in which jobs are announced before the actual release time of a job. We show that with sufficient advance notice, we can obtain a constant competitive ratio for proportionally weighted throughput {\it without any preemption}. However, this advance notice result does not extend to arbitrary C-Benevolent and D-Benevolent weight functions. Finally, we show that unlike interval scheduling, unweighted throughput using preemption with revoking admits no constant competitive ratio when the number of distinct processing times is unrestricted. More precisely, for instances with at most $k$ distinct processing times, we give a lower bound of $1/(k+1)$ and a deterministic $1/(2k)$-competitive algorithm.