Search code examples
algorithmgraphscheduling

Graph scheduling intersection

I need to calculate all possible intersections in workflow (directed acyclic graph). I tried to find efficient algorithm but was lack in finding. Looks like it's Parallel Scheduling theory.

For example I have graph:

enter image description here

I don't know time execution of each node, so I need to find all intersections:

  1. A
  2. B C
  3. B E F
  4. B E G
  5. B G
  6. B H
  7. D C
  8. D E F
  9. D E G
  10. D G
  11. D H
  12. H
  13. and others possible sets (updated after comments)

How I can calculate this intersections ?

Solution

  • To answer the question in part, for the problem in the question, there is no efficient algorithm (in the sense of a runtime bound which is polynomially bounded in the encoding length of the input) by the following class of examples.

    Let n be a nonnegative integer. Create a task digraph G=(V,E) with n+2 nodes as follows. Let s be the source node, which constitutes layer one, let t_1,...,t_n be n intermediate nodes at layer two, and let t be a terminal node at layer three, i.e.

    V := { s } union { t_i : i in { 1,...,n } } union { t }

    and connect layer one to layer two and layer two to layer three, i.e.

    E := { ( s, t_i ) : i in { 1,...,n } } union { ( t_i, t ) : { 1,...,n } }

    which intuitively means that the source is connected to all tasks and all tasks are connected to the terminal. Suppose that all tasks t_{i}, for each i in {1,...,n} have either processing time 1 or 2; the processing times of s and t don't matter. This means that potentially every combination of tasks t_{i}, for each i in {1,...,n}, can run simultaneously; however the cardinalty of the set of all combinations of tasks t_i (which is the power set of {t_1,...,t_n}) is 2^n, which is not polynomially bounded in n.

    That being said, perhaps the usual notion of 'polynomial runtime bound' does not apply here, as already the size of the output is not not polynomially bounded in the size of the input.