Tuesday, July 26, 2005

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