Minimizing the maximum lateness in real-time computations with extended deadlines

We present an algorithm for scheduling real-time computations with extended deadlines. The extended execution model allows part of a real-time computation to be executed after the primary deadline but before a secondary, or extended, deadline. The model can be used by real-time computations which must provide a timely result before a tight deadline but only need to finish the rest of the computation before a much later deadline. Although the computations have extended deadlines, it is still desirable to finish their executions as close to the primary deadlines as possible. We present an algorithm which minimizes the maximum lateness of any computation. We also show the complexity of our algorithm.