Operations and Supply Chain: Apply It 1

  • Describe concepts like inventory management, production scheduling, and optimization 

Critical Path Algorithm

The critical path algorithm allows you to create a priority list based on idea of critical paths.

How To: Critical Path Algorithm (version 1)

  1. Find the critical path.
  2. The first task in the critical path gets added to the priority list.
  3. Remove that task from the digraph.
  4. Repeat, finding the new critical path with the revised digraph.

Consider the scheduling problem represented by the digraph below.

a directed graph with seven nodes and directed edges connecting them. Each node is labeled T1 to T10 with a number in parentheses that could represent a time stamp or identifier. From the top left to the right and then down, the nodes and their connections are as follows: T1(6) has an arrow pointing to T5(5). T5(5) has arrows pointing to both T9(2), T10(7) and T8(3). T9(2) is the terminal node with no outgoing arrows. T2(3) has an arrow pointing to T6(10). T6(10) has arrows pointing to both T5(5) and T7(4). T8(3) has an arrow pointing to T10(7). T3(7) has an arrow pointing to T7(4). T7(4) has an arrow pointing to T10(7). T4(4) is isolated with no connections to or from it. The graph may represent a process flow, task dependencies in a project, or transactions in a database system. Nodes T1, T2, T5, and T3 represent starting points of various processes, with T9 and T10 as endpoints, and T4 being an independent entity.

 

The original digraph from Example 3 has critical path [latex]T2,T6,T5,T8,T10[/latex], so [latex]T2[/latex] gets added first to the priority list. Removing [latex]T_2[/latex] from the digraph, it now looks like:

a directed graph with seven nodes and directed edges connecting them. Each node is labeled T1 to T10 with a number in parentheses that could represent a time stamp or identifier. From the top left to the right and then down, the nodes and their connections are as follows: T1(6) has an arrow pointing to T5(5). T5(5) has arrows pointing to both T9(2), T10(7) and T8(3). T9(2) is the terminal node with no outgoing arrows. T6(10) has arrows pointing to both T5(5) and T7(4). T8(3) has an arrow pointing to T10(7). T3(7) has an arrow pointing to T7(4). T7(4) has an arrow pointing to T10(7). T4(4) is isolated with no connections to or from it. The graph may represent a process flow, task dependencies in a project, or transactions in a database system. Nodes T1, T5, and T3 represent starting points of various processes, with T9 and T10 as endpoints, and T4 being an independent entity.

 

Solution

The critical path (longest path) in the remaining digraph is now [latex]T_6,T_5,T_8,T_{10},[/latex] so [latex]T_6[/latex] is added to the priority list and removed.

a directed graph with seven nodes and directed edges connecting them. Each node is labeled T1 to T10 with a number in parentheses that could represent a time stamp or identifier. From the top left to the right and then down, the nodes and their connections are as follows: T1(6) has an arrow pointing to T5(5). T5(5) has arrows pointing to T9(2), T10(7) and T8(3). T9(2) is the terminal node with no outgoing arrows. T8(3) has an arrow pointing to T10(7). T3(7) has an arrow pointing to T7(4). T7(4) has an arrow pointing to T10(7) and T8(3). T4(4) is isolated with no connections to or from it.

 

Now there are two paths with the same longest length: [latex]T_1,T_5,T_8,T_{10}[/latex] and [latex]T_3,T_7,T_8,T_{10}[/latex]. We can add [latex]T_1[/latex] to the priority list (or [latex]T_3[/latex] – we usually add the one with smaller item number) and remove it, and continue the process.

I’m sure you can imagine that searching for the critical path every time you remove a task from the digraph would get really tiring, especially for a large digraph. In practice, the critical path algorithm is implementing by first working from the end backwards. This is called the backflow algorithm.

How To: Backflow Algorithm

  1. Introduce an “end” vertex, and assign it a time of [latex]0[/latex], shown in [brackets].
  2. Move backwards to every vertex that has an arrow to the end and assign it a critical time.
  3. From each of those vertices, move backwards and assign those vertices critical times. Notice that the critical time for the earlier vertex will be that task’s time plus the critical time for the later vertex.

Consider this segment of digraph.

A node labeled T1(5) pointing towards a node labeled T2(4), with [10] in red next to the node.

 

In this case, if [latex]T_2[/latex] has already been determined to have a critical time of [latex]10[/latex], then [latex]T_1[/latex] will have a critical time of [latex]5+10 = 15[/latex].

A node labeled T1(5) with [15] in red next to it pointing towards a node labeled T2(4), with [10] in red next to the node.

 

If you have already assigned a critical time to a vertex, replace it only if the new time is larger.

In the digraph below, [latex]T_1[/latex] should be labeled with a critical time of [latex]16[/latex], since it is the longer of [latex]5+10[/latex] and [latex]5+11[/latex].

A node labeled T1(5) pointing towards a node labeled T2(4), with [10] in red next to the node and a node labeled T3(5), with [11] in red next to the node.

 

Repeat until all vertices are labeled with their critical times.

One you have completed the backflow algorithm, you can easily create the critical path priority list by using the critical times you just found.