Technical Report Number 2007-536 Penalty Minimization in Scheduling a Set of Soft Real-Time Tasks ∗
Arezou Mohammadi, Selim G. Akl · 2007
A soft real-time task is one whose completion time is recommended by a specific deadline. However, should the deadline be missed, such a task is not considered to have failed; only the later it finishes, the higher the penalty that is paid. For a set of soft real-time tasks that are to be scheduled on a single machine under overload conditions, our objective is to minimize the total penalty paid. This optimization problem is NP-hard. In this paper, we prove a number of properties of any optimal scheduling algorithm for the problem. Then, we provide a number of heuristic algorithms which satisfy the properties obtained herein. Numerical simulations are presented to compare the penalty to be paid by the algorithms. We also determine an upper bound for the optimal solution to the problem. Numerical results that compare the upper bound with the optimal solution and the heuristic algorithms are provided.