We consider the problem of preemptive scheduling a set of periodically occurring jobs on a set of unrelated processors, that is, processors having different speeds for different jobs. We assume that each occurrence of a job has to be completely processed before the next occurrence of the same job. We provide a system of linear inequalities for testing the existence of a feasible schedule which can be solved in polynomial time. We then use the solution to this linear system, if any, for constructing a feasible schedule in a straightforward way.
A POLYNOMIAL FEASIBILITY TEST FOR PREEMPTIVE PERIODIC SCHEDULING OF UNRELATED PROCESSORS
BONUCCELLI, MAURIZIO ANGELO
1985-01-01
Abstract
We consider the problem of preemptive scheduling a set of periodically occurring jobs on a set of unrelated processors, that is, processors having different speeds for different jobs. We assume that each occurrence of a job has to be completely processed before the next occurrence of the same job. We provide a system of linear inequalities for testing the existence of a feasible schedule which can be solved in polynomial time. We then use the solution to this linear system, if any, for constructing a feasible schedule in a straightforward way.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
