Existence of Real-Time Multiprocessor Schedule
Y. Cho and S. Sahni, Scheduling Independent tasks with due times on a uniform Processor System, Jr. of the ACM, 1980


Presents an algorithm to preemptively schedule n tasks(with due dates) on m uniform processors whenever a solution exists in $O(n\log{n} + mn)$ time. 

Which is a stronger problem than I wanted to solve but still gives a polynomial algorithm, which answers my question.