Scheduling real-time computations with extended deadlines

Real-time scheduling problem is to find a feasible schedule in which every computation starts execution after its ready time, completes before its deadline and satisfies all of its precedence constraints. In many applications, some real-time job allows part of its computation to be finished after its primary deadline but before its eztended deadline. In this paper, we study the scheduling issues for real-time computations with extended 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. We study two variations of this problem. In the 6rst model, the system receives a penalty for each late soft part. In the second model, there is an extra computation overhead for each late soft part. For each model, we present algorithms to produce a feasible schedule.