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

作者：Tao, Ye^*; Chao, Zhijun; Xi, Yugeng

来源：International Multi-Conference of Engineers and Computer Scientists, China, 2009-03-18 to 2009-03-20.

• scheduling
• semi-online algorithm
• worst-case analysis
• competitive ratio
• real-time system

This paper presents a new kind of models defined as 1 vertical bar r(j), r(t)(1), vertical bar Sigma C-j, which covers a wide range of models in a real-time system such as periodic, aperiodic and sporadic task models. We provide a semi-online algorithm AOPT for such a model with a reasonable assumption. In its worst-case analysis, we demonstrate that the lower bound of the competitive 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 analysis, 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 introduction of some future information will improve the performance of an algorithm.

• 出版日期2009
• 单位上海交通大学