Algorithms for scheduling computations with secondary deadlines to minimize penalty

In many real-time applications, some job allows part of its computation to be executed after its primary deadline but before an extended, or secondary deadline. We study the scheduling issues for real-time computations with secondary deadlines. We call the part of a computation which must be completed before the primary deadline its hard part, and the rest its soft part. The soft part of a computation can be delayed after its primary deadline but must be finished before its secondary deadline. Although the computations have secondary deadlines, it is still desirable to finish the complete computations before their primary deadlines. Therefore, the system receives a penalty for each soft part that finishes after the primary deadline. We present scheduling algorithms for the model which minimizes the total penalty or the maximum penalty