Identifying Loops by Path Searching
(Gebala and Eppinger, 1991)

In path searching, information flow is traced either backwards or forwards until a task is encountered twice (Sargent and Westerberg, 1964). All tasks between the first and second occurrence of the task constitute a loop of information flow. When all loops have been identified, and all tasks have been scheduled, the sequencing is complete and the matrix is in block triangular form.

The figure, below, is a simple example. The path searching partition proceeds as follows:

a) The unpartitioned matrix is in its original order.

b) Task F does not depend on information from any other tasks as indicated by an empty row. Schedule task F first in the matrix and remove it from further consideration.

c) Task E does not provide  information to any tasks in the matrix as indicated by an empty column. Schedule task E last in the matrix and remove it from further consideration.

d) Now, no tasks have empty rows or columns. A loop exists and can be traced starting with any of the remaining tasks. In this case, we select task A (arbitrary) and trace its dependence on task C. Task C is simultaneously dependent upon information from task A. Since task A and task C are in a loop, collapse one into the other and represent them in a single, composite task (i.e. task CA).

e) Task CA has an empty column indicating that it is not part of any other loop. Schedule it last and remove it from further consideration.

f) Trace dependency starting with any unscheduled task: task B depends on task G which depends on task D which depends on task B. This final loop includes all the remaining unscheduled tasks.

g) The final partitioned matrix.

Example

Back to Tutorial Index