Offline scheduling fully determined arbitrary jobs in multiprocessor setting
I think it is going to be tough to find a more efficient algorithm than the one you already have.  You are getting close to requiring an online algorithm.  

I think a lot is known about the online version of this problem.  Take a look at:


  Dertouzos and Mok: Multiprocessor On-Line Scheduing of Hard-Real-Time Tasks, IEEE T. Software Eng., 15(12):1497-1506, 1979.


It is known that least laxity first (also known as least slack first) scheduling is an optimal on-line greedy scheduling algorithm for the multiprocessor case only when all the $a_i$ are the same (basically: all the tasks arrive at the same time, but they have different execution times and deadlines.)  Dertouzos and Mok show there is no online algorithm for the case that the $a_i$ are not known a-priori.

What I don't know is whether there is some least-slack-first algorithm similar to list scheduling.  There must be a reference about this, but I haven't found it in the small amount I've looked just now.  Slack is a dynamic quantity.  At any time $t$ for any job $i$ it is the difference between $d_i -t$ and however much work is remaining to be done on job $i$.  The slack of a job starts at the value $(d_i - a_i) - r_i$ and must be monotonically non-increasing.  On imagines that one could take all the jobs, sort them by their initial slack value, and then greedily schedule them in that order, and that (for the case where the processors are identical, there are no precedence constraints, the jobs are all single-threaded, and arbitrary preemption and job migration are permitted and have no cost) you might be able to prove something concrete about it.