Is Audsley's Scheme the Most Expressive Optimal Priority Assignment Algorithm?

For fixed priority scheduling, the allocation of priorities to the application's tasks is a fundamental activity. If all possible allocations have to be checked (to find the optimal one) then a total n! ordering must be examined (for n tasks). For any large n this is prohibitive. Fortunately for simple task models straightforward optimal priority schemes are available; for example rate monotonic for sporadic task sets with implicit deadlines, deadline monotonic for tasks with constrained deadlines and deadline-jitter monotonic for tasks with constrained deadlines and release jitter. Where these simple schemes are not applicable, for example with non-preemptive scheduling, or task sets with arbitrary deadlines or mixed criticality systems, there exists a scheme with n^2 complexity that is often applicable. This scheme was first proposed in 1991 and is generally known as Audsley's algorithm. Unfortunately not all task models have the prerequisites that allow this algorithm to be applied. Examples of such models are to be found in fixed priority multiprocessor scheduling. Often when Audsley's algorithm is found to be not applicable the only option remaining is to develop and use heuristics that aim for good, rather than optimal, priority orderings. This leads to the question being asked in this paper: if Audsley's algorithm is not applicable can an optimal priority assignment scheme only be found by enumerating all n! possibilities?