page581.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 168 行
HTML
168 行
<HTML><HEAD><TITLE>Application: Critical Path Analysis</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7828" HREF="page582.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7826" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7820" HREF="page580.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7830" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0016600000000000000000">Application: Critical Path Analysis</A></H1><P>In the introduction to this chapter it is statedthat there are myriad applications of graphs.In this section we consider one such application--<em>critical path analysis</em><A NAME=54654> </A>.Critical path analysis crops up in a number of different contexts,from the planning of construction projectsto the analysis of combinational logic circuits.<P>For example, consider the scheduling of activitiesrequired to construct a building.Before the foundation can be poured,it is necessary to dig a hole in the ground.After the building has been framed,the electricians and the plumberscan rough-in the electrical and water servicesand this rough-in must be completed before the insulation is put upand the walls are closed in.<P>We can represent the set of activitiesand the scheduling constraints usinga vertex-weighted, directed acyclic graph (DAG).Each vertex represents an activityand the weight on the vertex represents the time requiredto complete the activity.The directed edges represent the sequencing constraints.That is, an edge from vertex <I>v</I> to vertex <I>w</I>indicates that activity <I>v</I> must complete before <I>w</I> may begin.Clearly, such a graph must be <em>acyclic</em>.<P>A graph in which the vertices represent activitiesis called an <em>activity-node graph</em><A NAME=54657> </A>.Figure <A HREF="page581.html#figcritical1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows an example of of an activity-node graph.In such a graph it is understood that independent activitiesmay proceed in parallel.For example, after activity <I>A</I> is completed,activities <I>B</I> and <I>C</I> may proceed in parallel.However, activity <I>D</I> cannot begin until <em>both</em> <I>B</I> and <I>C</I> are done.<P><P><A NAME="55242"> </A><A NAME="figcritical1"> </A> <IMG WIDTH=575 HEIGHT=150 ALIGN=BOTTOM ALT="figure54660" SRC="img2457.gif" ><BR><STRONG>Figure:</STRONG> An activity-node graph.<BR><P><P>Critical path analysis answers the following questions:<OL><LI> What is the minimum amount of time needed to complete all activities?<LI> For a given activity <I>v</I>, is it possible to delay the completion of that activity without affecting the overall completion time? If yes, by how much can the completion of activity <I>v</I> be delayed?</OL><P>The activity-node graph is a vertex-weighted graph.However, the algorithms presented in the preceding sectionsall require edge-weighted graphs.Therefore, we must convert the vertex-weighted graphinto its edge-weighted <em>dual</em><A NAME=55248> </A>.In the dual graphthe edges represent the activities,and the vertices representthe commencement and termination of activities.For this reason, the dual graph is calledan <em>event-node graph</em><A NAME=55250> </A>.<P>Figure <A HREF="page581.html#figcritical2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the event-node graphcorresponding to the activity node graph given in Figure <A HREF="page581.html#figcritical1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Where an activity depends on more than one predecessorit is necessary to insert <em>dummy</em> edges.<P><P><A NAME="55604"> </A><A NAME="figcritical2"> </A> <IMG WIDTH=575 HEIGHT=136 ALIGN=BOTTOM ALT="figure55254" SRC="img2458.gif" ><BR><STRONG>Figure:</STRONG> The event-node graph corresponding to Figure <A HREF="page581.html#figcritical1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<BR><P><P>For example, activity <I>D</I> cannot commence until both <I>B</I> and <I>C</I> are finished.In the event-node graph vertex 2 represents the termination of activity <I>B</I>and vertex 3 represents the termination of activity <I>C</I>.It is necessary to introduce vertex 4 to represent the eventthat <em>both</em> <I>B</I> and <I>C</I> have completed.Edges <IMG WIDTH=40 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline72363" SRC="img2459.gif" > and <IMG WIDTH=41 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline72365" SRC="img2460.gif" > representthis synchronization constraint.Since these edges do not represent activities,the edge weights are zero.<P>For each vertex <I>v</I> in the event node graph we define two times.The first <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72369" SRC="img2461.gif" > is the<em>earliest event time</em><A NAME=55477> </A> for event <I>v</I>.It is the earliest time at which event <I>v</I> can occurassuming the first event begins at time zero.The earliest event time is given by<P><A NAME="eqngraphsetime"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation55478" SRC="img2462.gif" ><P>where <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline70715" SRC="img2201.gif" > is the <em>initial</em> event, <IMG WIDTH=33 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70633" SRC="img2179.gif" > is the set of incident edges on vertex <I>w</I>and <I>C</I>(<I>v</I>,<I>w</I>) is the weight on vertex (<I>v</I>,<I>w</I>).<P>Similarly, <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72385" SRC="img2463.gif" > is the<em>latest event time</em><A NAME=55487> </A> for event <I>v</I>.It is the latest time at which event <I>v</I> can occurThe latest event time is given by<P><A NAME="eqngraphsltime"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation55488" SRC="img2464.gif" ><P>where <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline72391" SRC="img2465.gif" > is the <em>final</em> event.<P>Given the earliest and latest event times for all events,we can compute time available for each activity.For example, consider an activity represented by edge (<I>v</I>,<I>w</I>).The amount of time available for the activity is <IMG WIDTH=58 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72395" SRC="img2466.gif" >and the time required for that activity is <I>C</I>(<I>v</I>,<I>w</I>).We define the <em>slack time</em><A NAME=55498> </A> for an activity asthe amount of time by which an activity can be delayedwith affecting the overall completion time of the project.The slack time for the activity represented by edge (<I>v</I>,<I>w</I>) is given by<P><A NAME="eqngraphsslack"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation55499" SRC="img2467.gif" ><P><P>Activities with zero slack are <em>critical</em><A NAME=55503> </A>.That is, critical activities must be completed on time--any delay affects the overall completion time.A <em>critical path</em><A NAME=55505> </A>is a path in the event-node graphfrom the initial vertex to the final vertexcomprised solely of critical activities.<P>Table <A HREF="page581.html#tblgraphscpa"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the results from obtained fromthe critical path analysis of the activity-node graphshown in Figure <A HREF="page581.html#figcritical1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The tabulated results indicate the critical path is<P> <IMG WIDTH=304 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath72323" SRC="img2468.gif" ><P><P><P><A NAME="55605"> </A><P> <A NAME="tblgraphscpa"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=5 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> activity </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>C</I>(<I>v</I>,<I>w</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72369" SRC="img2461.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72405" SRC="img2469.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>S</I>(<I>v</I>,<I>w</I>) </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>A</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>B</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>C</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>D</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>E</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 9 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 17 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>F</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 17 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>G</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 17 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 18 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Critical path analysis results for the activity-node graph in Figure <A HREF="page581.html#figcritical1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE></P></DIV><P><BR> <HR><UL> <LI> <A NAME="tex2html7831" HREF="page582.html#SECTION0016601000000000000000">Implementation</A></UL><HR><A NAME="tex2html7828" HREF="page582.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7826" HREF="page519.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7820" HREF="page580.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7830" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?