Excursions in Math

Scheduling: Critical Path Scheduling Example

Example

Use the critical path scheduling algorithm to to create a schedule for the following order requirement digraph.

Solution

The critical scheduling method will produce our priority list for us.

Longest path identified in red Priority List

order requirement digraph There are two critical paths of length 34: T2, T5, T6 and T3, T7, T6. Choose the one with smallest starting value: T3
Priority List: T3

Priority List: T3, T2

Priority List: T3, T2, T7

Priority List: T3, T2, T7, T5

Priority List: T3, T2, T7, T5, T1

order requirement digraph Priority List: T3, T2, T7, T5, T1, T6

Priority List: T3, T2, T7, T5, T1, T6, T4

Longest path identified in red	Priority List
	There are two critical paths of length 34: T2, T5, T6 and T3, T7, T6. Choose the one with smallest starting value: T3 Priority List: T3
	Priority List: T3, T2
	Priority List: T3, T2, T7
	Priority List: T3, T2, T7, T5
	Priority List: T3, T2, T7, T5, T1
	Priority List: T3, T2, T7, T5, T1, T6
	Priority List: T3, T2, T7, T5, T1, T6, T4

Now we have a priority list T3, T2, T7, T5, T1, T6, T4. Using this list and the list processing algorithm, we get the following schedule for three processors: