hardness of the URE/SURE scheduling

The input to a SURE scheduling problem is a (n+d)*m matrix, and we are to find the minimum running time of the system (with a reasonable aggrement on this statement).

n has to be >= 1.

If n=1, then we have a URE. The scheduling problem for n = 1 is as hard as the LP problem of d*m size.

When n>1, the problem is harder.

OTOH, d has to be >= 0

If d = 0. we have a digraph and the scheduling problem is a DFS!

if d = 1, we have a digraph, whose weights are scalars. This means that the scheduling problem is as hard as a APSP.

for d > 1, the problem becomes harder