General outline of the proof of optimality of Deadline-Monotonic
scheduling (for details, see Leung&Whitehead [1982]).

The proof is by contradiction: Assume that there is a task system
such that a non-DM priority assignment is feasible, while the DM
assignment is not. There must be two tasks with adjacent priorities
that are not in DM order. We show that these two task priorities
can be reversed without affecting the schedulability of the 
task set.

To show this, we assume a task set T1, ..., Tn, with decreasing
priority. Tasks Tk and Tk+1 have deadlines dk >= dk+1. We show
that the priorities of these two tasks can be switched.
1. No other tasks are affected by the switch.
2. The response time of Tk+1 is not increased by the switch.
3. We need to show that Tk does not miss the deadline after the
   switch. This can be shown using a rather simple argument
   about the amount of processing time done for the tasks
   T1, ..., Tk-1 during the interval [0, dk+1].