On-line Scheduling Algorithm for the Gravitational Task Model

Some applications for real-time scheduling have target demands in addition to the commonly used starttime and deadline constraints: a task should be executed at a target point in time for maximum utility, but can execute around this point, albeit at lower utility Examples for such applications include control and media processing. In this paper we present a scheduling algorithm for the gravitational task model that we proposed in [1], [2]. This model allows tasks to express their utility as a function of the point of execution and the target point. The proposed scheduler is divided into 2 phases: ordering and timing. The former uses a heuristic to order the jobs in the ready queue and the latter schedules the execution based on the equilibrium [1], [2]. The new ordering heuristic accounts for both acceptance ratio and utility accrual, hence achieving better results than the scheduler proposed in [1], [2]. Besides, the scheduler proposed here uses a heuristic for the ordering phase of complexity O(n x log(n)) and a timing phase of complexity O(n). These complexities represent a significant reduction compared to previous work. Moreover this paper contains an analysis of the complexity of the proposed scheduler and an evaluation through simulation.