Optimal resource assignment of preemptive periodic tasks on multiple processors

In this article we examine the problem of preemptively scheduling periodically occurring tasks on a system of parallel processors so as to maximize a linear function of the tasks completed. We show that polynomial time solutions exist for all the no-deadline problems, derive an O(n log n) algorithm for the preemptive parallel processor problem, and include results for minimization of number of processors and maximization of flexibility for handling additional tasks. We present lower and upper bounds on the number of preemptions. We show that all optimization problems with either arbitrary or next-request deadlines are NP-hard.