Abstract
We will explore a generalization of the real-time scheduling problem sometimes called the real-time throughput maximization problem. Our input is a sequence of jobs specified by their release time, deadline, and processing time. We assume that jobs are announced before or at their release time. At each time step, the algorithm must decide whether to schedule a job based on the information so far. The goal is to maximize the value of the sum of the processing times of jobs that finish before their deadline, often referred to as real-time throughput with proportional weights.
We extend this problem by defining a notion of (t)-advance-notice, a measure of how far in advance each job is announced relative to their processing time. We show that there exists a class of algorithms (\tau-\textsc{Persist}) parametrized by some value (\tau\in [1,\infty)). If an input sequence has (t)-advance-notice, (\tau-\textsc{Persist}) is (\frac{\tau - 1}{\tau^2 + \tau - 1})-competitive. In particular, we show that for any (t \leq \frac{1}{2}), there is an algorithm that achieves (\frac{t-t^2}{1+t-t^2})-competitiveness, and for any (t \geq \frac{1}{2}), there exists an algorithm that achieves (\frac{1}{5})-competitiveness. We also provide an upper bound for any algorithm relying on input sequences with (t)-advance-notice. We demonstrate that the competitive ratio of any algorithm can be at most (\frac{t}{2t+1}) against input sequences that have (t)-advance-notice. Notably, we show that regardless of the amount of advance notice given, no algorithm can achieve (\frac{1}{2})-competitiveness.
Blogger's Review: This study delves into the advance notice mechanism in real-time scheduling, revealing the impact of different notification times on scheduling competitiveness. It offers valuable theoretical guidance, providing new perspectives for the design of practical scheduling algorithms. The insights gained are particularly reference-worthy for optimizing scheduling in real-time systems.