Scheduling: Critical Path Scheduling

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.

Critical Path Scheduling

1. find a task that begins a critical path in the order requirement digraph. If there is a tie, choose the task with the lower number.
2. Place the task found in step 1 next on the list L.
3. Remove the task found in step 1, and all the edges attached to it, from the current order requirement digraph. This leaves a new order requirement digraph.
4. If there are no vertices left in the new order requirement digraph found in step 3, the procedure is complete and you have the priority list L. If there are vertices left, go to step 1.

The priority list found using critical path scheduling will hopefully produce a schedule which has an optimal or near optimal solution.

Longest path identified in red	Priority List
	T1
	T1, T2
	T1, T2, T3
	T1, T2, T3, T5
	T1, T2, T3, T5, T4
	T1, T2, T3, T5, T4, T7
	T1, T2, T3, T5, T4, T7, T6

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

This is not the optimal solution to the scheduling problem, but it is close. The optimal solution would take a time of 54 to complete the job if we had two processors available.