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$ – Yuval Filmus Dec 4 '17 at 22:05
  • $\begingroup$ Can you specify your problem in more details? $\endgroup$ – Yuval Filmus Dec 4 '17 at 22:05
  • $\begingroup$ @YuvalFilmus I added some more details. Let me know if you want me to clarify more. $\endgroup$ – Nilesh Hirani Dec 4 '17 at 22:15

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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