The Critical-Path Algorithm - H-SC
The Critical-Path Algorithm Lecture 34 Sections 8.3 - 8.4 Robb T. Koether Hampden-Sydney College Mon, Apr 20, 2015 Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 1 / 20
1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 2 / 20
Outline 1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 3 / 20
Definitions Definition (Critical Path for a Vertex) The critical path for a vertex is the path from that vertex to END with the longest processing time. Definition (Critical Path for a Project) The critical path for a project is the critical path from START to END. Definition (Critical Time) The critical time for a vertex or project is the processing time of its critical path. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 4 / 20
Example A(6) F(3) D(2) Start(0) B(5) G(3) End(0) C(7) E(5) H(4) The critical time of a project is the shortest possible time required to complete the project. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 5 / 20
Example A(6) F(3) D(2) Start(0) B(5) G(3) End(0) C(7) E(5) H(4) The critical time of a project is the shortest possible time required to complete the project. It is also the longest path (in terms of time) from START to END. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 5 / 20
Example A(6) F(3) D(2) Start(0) B(5) G(3) End(0) C(7) E(5) H(4) The critical time of a project is the shortest possible time required to complete the project. It is also the longest path (in terms of time) from START to END. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 5 / 20
Outline 1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 6 / 20
The Backflow Algorithm Definition (The Backflow Algorithm) The backflow algorithm finds the critical path by the following method. 1 Beginning with END and working back to START, find the critical time for each vertex. The critical time for a vertex is the processing time for that vertex plus the largest critical time of the vertices incident from that vertex. 2 The critical path for the project is the path from START to END whose edges connect each vertex to its successor with the greatest critical time. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 7 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(6) F(3) D(2) Start(0) B(5) G(3) End(0) C(7) E(5) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(6) F(3) D(2) Start(0) B(5) G(3) End(0) C(7) E(5) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(6) F(3) D(5) Start(0) B(5) G(3) End(0) C(7) E(9) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(11) F(3) D(5) Start(0) B(14) G(3) End(0) C(16) E(9) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(11) F(3) D(5) Start(16) B(14) G(3) End(0) C(16) E(9) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
The Backflow Algorithm Example (The Backflow Algorithm) A(11) F(3) D(5) Start(16) B(14) G(3) End(0) C(16) E(9) Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm H(4) Mon, Apr 20, 2015 8 / 20
Outline 1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 9 / 20
The Critical-Path Algorithm Definition (The Critical-Path Algorithm) The critical-path algorithm creates a schedule by the following method. 1 Use the backflow algorithm to find the critical time of every task in the project. 2 Create a priority list with the tasks listed in order of decreasing critical time. 3 Use the priority list to create a schedule. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 10 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) Start(16) B(14) G(3) End(0) C(16) E(9) H(4) The priority list is C, B, A, E, D, H, F , G. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 11 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 0 Robb T. Koether (Hampden-Sydney College) 5 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) 0 Robb T. Koether (Hampden-Sydney College) 5 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) 5 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) A(6) 5 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 D(2) 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 H(4) D(2) 10 The Critical-Path Algorithm 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 D(2) 10 The Critical-Path Algorithm H(4) F(3) 15 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 D(2) 10 The Critical-Path Algorithm H(4) F(3) 15 G(3) 20 Mon, Apr 20, 2015 12 / 20
Example Example (The Critical-Path Algorithm) A(11) F(3) D(5) B(14) Start(16) G(3) End(0) C(16) H(4) E(9) Priority list: C, B, A, E, D, H, F , G Processor 1 Processor 2 C(7) B(5) 0 Robb T. Koether (Hampden-Sydney College) E(5) A(6) 5 D(2) 10 The Critical-Path Algorithm H(4) F(3) 15 G(3) 20 Mon, Apr 20, 2015 12 / 20
Outline 1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 13 / 20
Example (Exercise 55) Task A B C D E F G H J Robb T. Koether (Hampden-Sydney College) Precedencent Tasks B C, G D H F H Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Mon, Apr 20, 2015 14 / 20
Example (Exercise 55) A(10) B(5) C(4) D(1) E(8) Start(0) End(0) G(7) F(3) H(1) J(6) Schedule the tasks using 2 processors. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 15 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 8 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 8 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 9 8 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 13 9 8 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 13 9 8 16 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 13 9 8 16 17 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 18 13 9 8 16 17 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) Task A B C D E F G H J Precedencent Tasks B C, G D H F H Robb T. Koether (Hampden-Sydney College) Processing Time 10 5 4 1 8 3 7 1 6 The Critical-Path Algorithm Critical Time 10 18 13 9 8 20 16 17 6 Mon, Apr 20, 2015 16 / 20
Example (Exercise 55) A(10) B(18) C(13) D(9) E(8) Start(20) End(0) G(16) F(20) H(17) J(6) Schedule the tasks using 2 processors. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 17 / 20
Example (Exercise 55) A(10) B(18) C(13) D(9) E(8) Start(20) End(0) G(16) F(20) H(17) J(6) Schedule the tasks using 3 processors. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 18 / 20
Outline 1 Critical Paths 2 The Backflow Algorithm 3 The Critical-Path Algorithm 4 Example 5 Assignment Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 19 / 20
Assignment Assignment Chapter 8: Exercises 49, 52, 53, 56. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 20 / 20
Definition (Critical Path for a Project) Thecritical path for a projectis the critical path from START to END. Definition (Critical Time) Thecritical timefor a vertex or project is the processing time of its critical path. Robb T. Koether (Hampden-Sydney College) The Critical-Path Algorithm Mon, Apr 20, 2015 4 / 20
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được
Le genou de Lucy. Odile Jacob. 1999. Coppens Y. Pré-textes. L’homme préhistorique en morceaux. Eds Odile Jacob. 2011. Costentin J., Delaveau P. Café, thé, chocolat, les bons effets sur le cerveau et pour le corps. Editions Odile Jacob. 2010. Crawford M., Marsh D. The driving force : food in human evolution and the future.
the American Board of Radiology (ABR) Core and Certifying examinations administered between January 1 – December 31, 2018. The guide has undergone a few minor changes compared to the 2018 version, which was significantly revised com- pared to earlier versions, reflecting changes in NIS content on the examinations. The primary change in this study guide is the addition of Core Concepts of .
