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

In this paper, we propose a new preemptive scheduling algorithm which belongs to a new family of real-time service oriented scheduling problems. As the complementarity of our previous non-preemptive algorithm, real time tasks are scheduled preemptively with the objective of maximizing the total utility this time. 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 a preemptive scheduling heuristics to judiciously accept, schedule, and abort real-time services when necessary to maximize the accrued utility. The new scheduling algorithm has a much better performance than an earlier scheduling approach based on a similar model does. Our extensive experimental results show that our proposed preemptive algorithms can outperform the related non-preemptive counterpart, which is a significant improvement compared with the scheduling pair proposed by Yu et al..