{"id":9823,"date":"2023-10-24T17:24:31","date_gmt":"2023-10-24T17:24:31","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=9823"},"modified":"2024-10-18T21:00:57","modified_gmt":"2024-10-18T21:00:57","slug":"operations-and-supply-chain-apply-it-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/operations-and-supply-chain-apply-it-1\/","title":{"raw":"Operations and Supply Chain: Apply It 1","rendered":"Operations and Supply Chain: Apply It 1"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Describe concepts like inventory management, production scheduling, and optimization\u00a0<\/li>\r\n<\/ul>\r\n<\/section>\r\n<h2 class=\"lt-math-34214 editable\">Critical Path Algorithm<\/h2>\r\n<p class=\"lt-math-34214\">The <strong>critical path algorithm<\/strong> allows you to create a priority list based on idea of critical paths.<\/p>\r\n<section class=\"textbox questionHelp\">\r\n<p><strong>How To: Critical Path Algorithm (version 1)<\/strong><\/p>\r\n<ol>\r\n\t<li class=\"lt-math-34214\">Find the critical path.<\/li>\r\n\t<li class=\"lt-math-34214\">The first task in the critical path gets added to the priority list.<\/li>\r\n\t<li class=\"lt-math-34214\">Remove that task from the digraph.<\/li>\r\n\t<li class=\"lt-math-34214\">Repeat, finding the new critical path with the revised digraph.<\/li>\r\n<\/ol>\r\n<\/section>\r\n<section class=\"textbox example\">\r\n<p>Consider the scheduling problem represented by the digraph below.<\/p>\r\n<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39331\/sc4.svg?revision=1&amp;size=bestfit&amp;width=360&amp;height=248\" alt=\"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.\" width=\"261\" height=\"180\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nThe 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:<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39339\/sc5.svg?revision=1&amp;size=bestfit&amp;width=340&amp;height=234\" alt=\"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.\" width=\"261\" height=\"180\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<strong>Solution<\/strong> <br \/>\r\n<br \/>\r\nThe 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.<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39340\/sc6.svg?revision=1&amp;size=bestfit&amp;width=350&amp;height=241\" alt=\"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. \" width=\"261\" height=\"180\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nNow 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] \u2013 we usually add the one with smaller item number) and remove it, and continue the process.<\/section>\r\n<section>I\u2019m 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\u00a0<b>backflow algorithm<\/b>.<\/section>\r\n<section class=\"textbox questionHelp\">\r\n<p><b>How To: Backflow Algorithm<\/b><\/p>\r\n<ol>\r\n\t<li class=\"lt-math-34214\">Introduce an \u201cend\u201d vertex, and assign it a time of [latex]0[\/latex], shown in [brackets].<\/li>\r\n\t<li class=\"lt-math-34214\">Move backwards to every vertex that has an arrow to the end and assign it a critical time.<\/li>\r\n\t<li class=\"lt-math-34214\">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\u2019s time plus the critical time for the later vertex.<\/li>\r\n<\/ol>\r\n<\/section>\r\n<section class=\"textbox example\">\r\n<p>Consider this segment of digraph.<\/p>\r\n<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39341\/sc7.svg?revision=1&amp;size=bestfit&amp;width=242&amp;height=38\" alt=\"A node labeled T1(5) pointing towards a node labeled T2(4), with [10] in red next to the node.\" width=\"192\" height=\"30\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p class=\"lt-math-34214\">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].<\/p>\r\n<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39342\/sc8.svg?revision=1&amp;size=bestfit&amp;width=245&amp;height=38\" alt=\"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.\" width=\"192\" height=\"30\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>If you have already assigned a critical time to a vertex, replace it only if the new time is larger.<\/p>\r\n<\/section>\r\n<section class=\"textbox example\">\r\n<p>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].<\/p>\r\n<center><img class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39343\/sc9.svg?revision=1&amp;size=bestfit&amp;width=242&amp;height=87\" alt=\"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.\" width=\"193\" height=\"69\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Repeat until all vertices are labeled with their critical times.<\/p>\r\n<\/section>\r\n<p>One you have completed the backflow algorithm, you can easily create the critical path priority list by using the critical times you just found.<\/p>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Describe concepts like inventory management, production scheduling, and optimization\u00a0<\/li>\n<\/ul>\n<\/section>\n<h2 class=\"lt-math-34214 editable\">Critical Path Algorithm<\/h2>\n<p class=\"lt-math-34214\">The <strong>critical path algorithm<\/strong> allows you to create a priority list based on idea of critical paths.<\/p>\n<section class=\"textbox questionHelp\">\n<p><strong>How To: Critical Path Algorithm (version 1)<\/strong><\/p>\n<ol>\n<li class=\"lt-math-34214\">Find the critical path.<\/li>\n<li class=\"lt-math-34214\">The first task in the critical path gets added to the priority list.<\/li>\n<li class=\"lt-math-34214\">Remove that task from the digraph.<\/li>\n<li class=\"lt-math-34214\">Repeat, finding the new critical path with the revised digraph.<\/li>\n<\/ol>\n<\/section>\n<section class=\"textbox example\">\n<p>Consider the scheduling problem represented by the digraph below.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39331\/sc4.svg?revision=1&amp;size=bestfit&amp;width=360&amp;height=248\" alt=\"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.\" width=\"261\" height=\"180\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>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:<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39339\/sc5.svg?revision=1&amp;size=bestfit&amp;width=340&amp;height=234\" alt=\"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.\" width=\"261\" height=\"180\" \/><\/div>\n<p>&nbsp;<\/p>\n<p><strong>Solution<\/strong> <\/p>\n<p>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.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39340\/sc6.svg?revision=1&amp;size=bestfit&amp;width=350&amp;height=241\" alt=\"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.\" width=\"261\" height=\"180\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>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] \u2013 we usually add the one with smaller item number) and remove it, and continue the process.<\/section>\n<section>I\u2019m 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\u00a0<b>backflow algorithm<\/b>.<\/section>\n<section class=\"textbox questionHelp\">\n<p><b>How To: Backflow Algorithm<\/b><\/p>\n<ol>\n<li class=\"lt-math-34214\">Introduce an \u201cend\u201d vertex, and assign it a time of [latex]0[\/latex], shown in [brackets].<\/li>\n<li class=\"lt-math-34214\">Move backwards to every vertex that has an arrow to the end and assign it a critical time.<\/li>\n<li class=\"lt-math-34214\">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\u2019s time plus the critical time for the later vertex.<\/li>\n<\/ol>\n<\/section>\n<section class=\"textbox example\">\n<p>Consider this segment of digraph.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39341\/sc7.svg?revision=1&amp;size=bestfit&amp;width=242&amp;height=38\" alt=\"A node labeled T1(5) pointing towards a node labeled T2(4), with [10] in red next to the node.\" width=\"192\" height=\"30\" \/><\/div>\n<p>&nbsp;<\/p>\n<p class=\"lt-math-34214\">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].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39342\/sc8.svg?revision=1&amp;size=bestfit&amp;width=245&amp;height=38\" alt=\"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.\" width=\"192\" height=\"30\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>If you have already assigned a critical time to a vertex, replace it only if the new time is larger.<\/p>\n<\/section>\n<section class=\"textbox example\">\n<p>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].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"internal alignnone\" src=\"https:\/\/math.libretexts.org\/@api\/deki\/files\/39343\/sc9.svg?revision=1&amp;size=bestfit&amp;width=242&amp;height=87\" alt=\"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.\" width=\"193\" height=\"69\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Repeat until all vertices are labeled with their critical times.<\/p>\n<\/section>\n<p>One you have completed the backflow algorithm, you can easily create the critical path priority list by using the critical times you just found.<\/p>\n","protected":false},"author":15,"menu_order":27,"template":"","meta":{"_candela_citation":"[]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":92,"module-header":"apply_it","content_attributions":[],"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/9823"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":9,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/9823\/revisions"}],"predecessor-version":[{"id":14951,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/9823\/revisions\/14951"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/92"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/9823\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=9823"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=9823"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=9823"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=9823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}