Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)?


  • The processors are Uniform parallel machines
  • Job preemption is permitted
  • Job migration is permitted
  • Job parallelism is forbidden

EDIT: Let there be $n$ jobs $J = \{j_1, j_2,\text{...}, j_n\}$ and $m$ no of processors $P = \{p_1, p_2,\text{...}, p_m\}$. Each job $j_i$ has a task time $t_i$(amount of work it would take to complete it) and due time $d_i$. Each processor has a constant speed $s_i$(amount of work it does per unit time). Each task must be completed before its due time.

I am interested to know about an algorithm with can check feasibility of a schedule in polynomial time.

  • $\begingroup$ An algorithm probably exists – I suspect you're interested in an efficient algorithm. $\endgroup$ Commented Dec 4, 2017 at 22:05
  • $\begingroup$ Can you specify your problem in more details? $\endgroup$ Commented Dec 4, 2017 at 22:05
  • $\begingroup$ @YuvalFilmus I added some more details. Let me know if you want me to clarify more. $\endgroup$ Commented Dec 4, 2017 at 22:15

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.