# Existence of Real-Time Multiprocessor Schedule

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)?

Assumptions:

• 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.

• An algorithm probably exists – I suspect you're interested in an efficient algorithm. – Yuval Filmus Dec 4 '17 at 22:05
• Can you specify your problem in more details? – Yuval Filmus Dec 4 '17 at 22:05
• @YuvalFilmus I added some more details. Let me know if you want me to clarify more. – Nilesh Hirani Dec 4 '17 at 22:15

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.