Parallel Task Scheduling

STGR Example File

Definitions:

 

EST--Earliest Start Time

ECT--Earliest Completion Time

LAST--Latest Start Time

LACT--Latest Completion Time

FP--Favorite Predecessor

DAG--Directed Acyclic Graph

 

Detailed descriptions of the definitions can be found in the algorithm pdf.

Task         Level       EST         ECT         LAST      LACT      FP

0               40             0               0               0               0               --

1               40             0               3               0               3               0

2               28             3               6               4               7               1

3               37             3               7               3               7               1

4               35             3               5               3               5               1

5               16             6               7               16             17             2

6               25             6               16             7               17             2

7               33             7               27             7               27             3

8               15             16             23             18             25             6

9               13             27             32             27             32             7

10             8               32             40             32             40             9

11             0               40             40             40             40             10

 

The schedule length for the input DAG is 40

 

Processor 1: Task 11 -> Task 10 -> Task 9 -> Task 7 -> Task 3 -> Task 1 -> Task 0

 

Processor 2: Task 8 -> Task 6 -> Task 2 -> Task 1

 

Processor 3: Task 5 -> Task 1

 

Processor 4: Task 4 -> Task 1