Properties of the ML(n) policy for scheduling jobs with real-time constraints

The behavior of two policies for scheduling customers with deadlines until the beginning of service onto multiprocessors is studied. Both policies attempt to approximate the performance of the minimum laxity (ML) scheduling policy without incurring its complete overhead. This is accomplished by dividing the queue into two queues-one, of maximum size n>0, managed using the minimum laxity policy and another of unbounded size managed in a first in first out manner. One policy, F/ML(n) place the ML queue at the front, i.e., customer finding n or more in the system enter the FIFO queue which in turn feeds the ML queue. The other policy, ML(n )/F places the ML queue at the back, i.e., arriving customers enter the ML queue, and if the total number in the system exceeds n, forces one customer from the ML queue to the FIFO queue. It is shown that these seemingly dissimilar policies exhibit exactly the same behavior for a fixed value of n both when customers are allowed to be discarded when they miss their deadlines before entering service and when they are not allowed to be discarded. Monotonicity properties are also established for both policies, with and without discards