On-line scheduling of real-time services with profit and penalty

On-line scheduling of real-time services with profit and penalty Conference

Liu, S, Quan, G, Ren, S. (2011). On-line scheduling of real-time services with profit and penalty . 1476-1481. 10.1145/1982185.1982501

In this paper, we study a new family of real-time service oriented scheduling problems. The real time tasks are scheduled non preemptively with the objective of maximizing the total utility. Different from the traditional utility accrual scheduling problem that each task is associated with only a single time utility function (TUF), two different TUFs - -a profit TUF and a penalty TUF - -are associated with each task, to model the real-time services that not only need to reward the early completions but also need to penalize the abortions or deadline misses. We present two scheduling heuristics to judiciously accept, schedule, and abort real-time services when necessary to maximize the accrued utility. Our extensive experimental results show that our proposed algorithms can significantly outperform the traditional scheduling algorithms such as the Earliest Deadline First (EDF), the traditional utility accrual scheduling algorithms and an earlier scheduling approach based on a similar model. © 2011 ACM.