A Near-Optimal Semi-Online Algorithm for Maximizing Throughput Scheduling Problem ⁄

This paper presents a new kind of models deflned as 1jrj;r 1 t;Cj P Cj, which covers a wide range of models in a real-time system such as periodic, ape- riodic and sporadic task models. We provide a semi- online algorithm AOPT for such a model with a rea- sonable assumption. In its worst-case analysis, we demonstrate that the lower bound of the competi- tive ratio by AOPT equals to 1:5387 while the upper bound is 1:57, which gives rise to a narrow gap of 0:0313. In addition, we generate and utilize a novel proving technique in the process of upper bound anal- ysis, the essence of which is to transform an arbitrary instance to the one with a computable performance ratio. Through such process, we argue that the intro- duction of some future information will improve the performance of an algorithm.