New Lectures5&6&7 PM Scheduling IP ENCE603 Ext Instructor
ENCE 603Management Science Applications in ProjectManagementLectures 5-7Project Management LP Modelsin Scheduling, Integer ProgrammingSpring 2009Instructor: Dr. Steven A. Gabrielwww.eng.umd.edu/ sgabriel1Copyright 2008, Dr. Steven A. GabrielOutline Project SchedulingCritical Path Method (CPM)AON and AOA methodsProject CrashingPrecedence Diagramming Method (PDM)Gantt Charts2Copyright 2008, Dr. Steven A. Gabriel1
Project Networks Project activities described by a networkCan use the activity-on-node (AON) modelNodes are activities, arrows (arcs) indicate the precedencerelationshipsCould also consider the activity-on-arc (AOA) model which hasarcs for activities with nodes being the starting and ending pointsAON used frequently in practical, non-optimization situations,AOA is used in optimization settingsFirst AON, then AOAMain idea for both is to determine the critical path (e.g., taskswhose delay will cause a delay for the whole project)3Copyright 2008, Dr. Steven A. GabrielProject Networks Sample project network (AON) (read left to right)Dashed lines indicate dummy activitiesKey: Activity, Duration (days)4Copyright 2008, Dr. Steven A. Gabriel2
Network Analysis Network Scheduling:Main purpose of CPM is to determine the “critical path”Critical path determines the minimum completion time for a projectUse forward pass and backward pass routines to analyze theproject networkNetwork Control:Monitor progress of a project on the basis of the network scheduleTake correction action when required “Crashing” the project Penalty/reward approach5Copyright 2008, Dr. Steven A. GabrielActivity on Node (AON)Representation of ProjectNetworks6Copyright 2008, Dr. Steven A. Gabriel3
Project NetworksA: Activity identification (node)ES: Earliest starting timeEC: Earliest completion timeLS: Latest starting timeLC: Latest completion timet: Activity durationP(A): set of predecessor nodes to node AS(A): set of successor nodes to node A7Copyright 2008, Dr. Steven A. GabrielProject Networks In tabular ple ComputationsES(A) Max{EC(j), j in P(A)} EC(start) 0EC(A) ES(A) tA 0 2 2ES(B) EC(start) 0EC(B) ES(B) tB 0 6 6ES(F) EC(A) 2EC(F) ES(F) 4 6, opyright 2008, Dr. Steven A. Gabriel4
Project Networks Notation: Above node ES(i), EC(i), below node LS(i),LC(i)Zero project slack convention in e ComputationsLC(F) Min{LS(i), i in S(F))} 11LS(F) LC(F)-tF 11-4 7etc.9Copyright 2008, Dr. Steven A. GabrielProject Networks During the forward pass, it is assumed that each activity willbegin at its earliest starting timeAn activity can begin as soon as the last of its predecessorshas finishedC must wait for both A and B to finish before it can startCompletion of the forward pass determines theCearliest completion time of the projectAB During the backward pass, it is assumed that each activitybegins at its latest completion timeEach activity ends at the latest starting time of the firstactivity in the project network10Copyright 2008, Dr. Steven A. Gabriel5
Project Networks Note:1 first node (activity),n last node,i,j arbitrary nodes,P(i) immediate predecessors of node i, S(j) immediatesuccessors of node j, Tp project deadline time41 325Rule 1: ES(1) 0 (unless otherwise stated)Rule 2: ES(i) Max j in P(i) {EC(j)}P(3) {1,2}S(3) {4,5}i1ii2 Why do we use “max” of thepredecessor EC’s in rule 2?i311Copyright 2008, Dr. Steven A. GabrielProject NetworksRule 3: EC(i) ES(i) tiRule 4: EC(Project) EC(n)Rule 5: LC(Project) EC(Project) “zero project slack convention” (unlessotherwise stated for example, see Rule 6)Rule 6: LC(Project) TpRule 7: LC(j) Min i in S(j) LS(i)Rule 8: LS(j) LC(j)-tjj1 Why do we use “min” inthe successor LS’s in rule7?jj2j312Copyright 2008, Dr. Steven A. Gabriel6
Project Networks Total Slack: Amount of time an activity may be delayed fromits earliest starting time without delaying the latest completiontime of the projectTS(j) LC(j)-EC(j) or TS(j) LS(j)-ES(j)Those activities with the minimum total slack are called thecritical activities (e.g., “kitchen cabinets”)Examples of activities that might have slackFree Slack: Amount of time an activity may be delayed fromits earliest starting time without delaying the starting time ofany of its immediate successors.FS(j) Min i in S(j) {ES(i)-EC(j)Let’s consider the sample network relative to critical activitiesand slack times13Copyright 2008, Dr. Steven A. GabrielCPM-Determining the CriticalPath AONStep 1: Complete the forward passStep 2: Identify the last node in the network as a critical activityStep 3: If activity i in P(j) and activity j is critical, check ifEC(i) ES(j). If yes Î activity i is critical. When all i in P(j)done, mark j as completedStep 4: Continue backtracking from each unmarked node until thestart node is reached14Copyright 2008, Dr. Steven A. Gabriel7
CPM-Forward Pass -4DA3EC5FA4GB,D,E2E,5Notation: Above node ES(i), EC(i)Sample ComputationsES(A) Max{EC(j), j in P(A)} EC(start) 0EC(A) ES(A) tA 0 2 2ES(B) EC(start) 0EC(B) ES(B) tB 0 6 6ES(F) EC(A) 2EC(F) ES(F) 4 6, etc.15Copyright 2008, Dr. Steven A. GabrielCPM-Backward Pass Example AON Notation: Above node ES(i), EC(i), below node LS(i),LC(i)Zero project slack convention in e ComputationsLC(F) Min{LS(i), i in S(F))} 11LS(F) LC(F)-tF 11-4 7etc.16Copyright 2008, Dr. Steven A. Gabriel8
CPM-Slacks and the Critical Path AON Total Slack: Amount of time an activity may be delayed fromits earliest starting time without delaying the latest completiontime of the projectTS(j) LC(j)-EC(j) or TS(j) LS(j)-ES(j)Those activities with the minimum total slack are called thecritical activities.Examples of activities that might have slackFree Slack: Amount of time an activity may be delayed fromits earliest starting time without delaying the starting time ofany of its immediate successors.FS(j) Min i in S(j) {ES(i)-EC(j)}Other notions of slack time, see Badiru-PulatLet’s consider the sample network relative to critical activitiesand slack times17Copyright 2008, Dr. Steven A. GabrielCPM Analysis for Sample Network ity?A202466-2 4Min{2,2}-2 0NoB606399-6 3Min{9}-6 3NoC404044-4 0Min{4}-4 0YESD325699-5 4Min{9}-5 4NoE549499-9 0Min{9}-9 0YESF42671111-6 5Min{11}-6 5NoG291191111-11 0Min{11}-11 50,44,90,42,5F,47,119,11G,2Total Project SlackTS(1) TS(C) TS(E) TS(G) TS(n) 011,11end11,119,1118Copyright 2008, Dr. Steven A. Gabriel9
Project Networks When results of a CPM analysis are matched up with acalendar, then we obtain a project scheduleGantt chart is a popular way to present this scheduleUsing the ES times from the sample AON project network, wehave the following Gantt chart(could also use latest completion times as well, extreme casewhen all slack times are fully used) 19Copyright 2008, Dr. Steven A. GabrielProject NetworksGFEDCBA1 2345678910 11DaysNote, Gantt chart shows for example:Starting time of F can be delayed until day 7 (TS 5) w/o delaying overall projectAlso, A, D, or both may be delayed by a combined total of four days (TS 4) w/odelaying the overall projectB may be delayed up to 3 days without affecting the overall project completion timeCan ignore precedence arrows (better20for large networks)Copyright 2008, Dr. Steven A. Gabriel10
Activity on Arc (AOA)Representation of ProjectNetworks21Copyright 2008, Dr. Steven A. GabrielProject Networks: Activity on Arc(AOA) RepresentationNodeNodeijarc(i,j) activity(i,j) Nodes represent the realizations of some milestones (events)of the projectArcs represent the activitiesNode i, the immediate predecessor node of arc(i,j) is the startnode for the activityNode j, the immediate successor node of arc(i,j) is the endnode for the activityWant to determine the critical path of activities, i.e., thosewith the least slack22Copyright 2008, Dr. Steven A. Gabriel11
Activity on Arc (AOA) Representation The early event time for node i, ET(i), is the earliest time at which the eventcorresponding to node i can occurThe late event time for node i, LT(i), is the latest time at which the eventcorresponding to node i can occur w/o delaying the completion of theprojectLet tij be the duration of activity (i,j)The total float (slack) TF(i,j) of activity (i,j) is the amount by which thestarting time of (i,j) could be delayed beyond its earliest possible startingtime w/o delaying the completion of the project (assuming no otheractivities are delayed)TF(i,j) LT(j)-ET(i)-tijThe free float of (i,j), FF(i,j) is the amount by which the starting time ofactivity (i,j) can be delayed w/o delaying the start of any later activitybeyond its earliest possible starting timeFF(i,j) ET(j)-ET(i)-tij23Copyright 2008, Dr. Steven A. GabrielAOA Network Structure The network is acyclic (o/w an activity would precede itself)1 23Each node should have at least one arc directed into the nodeand one arc directed out of the node (with the exception of thestart and end nodes), why?Start node has does not have any arc into it and the end nodehas no arc out of itAll of the nodes and arcs of the network have to be visited(that is realized) in order to complete the project, why?24Copyright 2008, Dr. Steven A. Gabriel12
AOA Network Structure If a cycle exists (due perhaps to an error in thenetwork construction), this will lead to cycling in theproceduresMore specifically, critical path calculations will notterminateNeed a procedure to detect cycles in the projectnetwork (e.g., Depth-First Search method)25Copyright 2008, Dr. Steven A. GabrielRules in AOA Networks1. Node 1 represents the start of the project. An arc should leadfrom node 1 to represent each activity that has no predecessors.2. A node (called the finish or end node) representing completion ofthe project should be included in the network.3. Number the nodes in the network so that the node representing thecompletion of an activity always has a larger number than thenode for the start of an activity (more than 1 way to do this).4. An activity should not be represented by more than one arc in thenetwork.5. Two nodes can be connected by at most one arc.26Copyright 2008, Dr. Steven A. Gabriel13
Small Sample ProjectActivity Predecessor DurationA-2B-6C-4DA3EC5FA4GB,D,E227Copyright 2008, Dr. Steven A. GabrielSmall Sample Project AOA28Copyright 2008, Dr. Steven A. Gabriel14
Using Linear Programming toFind a Critical Path Let xj the time that the event corresponding to node j occursLet tij the time to complete activity (i,j)For each activity (i,j), we know that before node j occurs, nodei must occur and activity (i,j) must be completed x j xi tij , (i, j ) Let 1 be the index of the start nodeLet F be the index of the finish node (i.e., when the project iscompleted)LP objective function is to minimize xF-x1, i.e., the total projecttime29Copyright 2008, Dr. Steven A. GabrielUsing Linear Programming toFind a Critical PathMin x5 – x1s.t.A) x2 x1 2B) x4 x1 6C) x3 x1 4D) x4 x2 3E) x4 x3 5F) x5 x2 4G) x5 x4 2Variables unrestricted in sign30Copyright 2008, Dr. Steven A. Gabriel15
Using Linear Programming toFind a Critical PathMin x5 - x1s.t.A) x2 - x1 B) x4 - x1 C) x3 - x1 D) x4 - x2 E) x4 - x3 F) x5 - x2 G) x5 - x4 endfree x1free x2free x3free x4free x52643542OBJECTIVE FUNCTION 0009.0000004.00000011.00000REDUCED right 2008, Dr. Steven A. GabrielUsing Linear Programming toFind a Critical PathMin x5 - x1s.t.A) x2 - x1 B) x4 - x1 C) x3 - x1 D) x4 - x2 E) x4 - x3 F) x5 - x2 G) x5 - x4 endfree x1free x2free x3free x4free x52643542ROWSLACK OR .000000F)1.000000G)0.000000DUAL 000000-1.00000032Copyright 2008, Dr. Steven A. Gabriel16
Using Linear Programming toFind a Critical Path For each variable with zero value and zero reduced cost thereis an alternative optimal solution.For each constraint with zero slack and zero dual variablethere is an alternative optimal solution.For each constraint with a dual price of –1, increasing theduration of the activity corresponding to that constraint byone day will increase the duration of the project by one day.Those constraints identify the critical activities. 33Copyright 2008, Dr. Steven A. GabrielAOA Project Network: After-Work-Hours Choresstart1aid3b4287dummy arcjecg65kh10l9dummy arcfActivityDescriptionImmediate PredecessorsaDad, Mom, and son arrive home in thesame car-bDad and Mom change clothescSon watches TVaadMom warns up the food*beDad sets the tablebfSon does homework**cdgMom fixes saladhThe family eats dinnere,f,giDad loads the dishwasherhjMom checks son’s homeworkhkSon practices (insert musicalinstrument name here)hlAll go to son’s basketball gamei,j,kmAll wash up and go to bedl11mend12*For politically correct projectnetworks, “Mom” and “Dad”are interchangeable.** In a perfect world, activityf precedes activity c!34Copyright 2008, Dr. Steven A. Gabriel17
Dummy Arcs in AOA Networks Since activities:i (Dad loads dishwasher),j (Mom checks son’s homework), and k(son practices musical instrument)all have the same predecessor activity h (family eats dinner) andthe same immediate successor, activity l (go to basketball game),this would mean 3 parallel arcs between nodes 7 and 10An activity network allows only one arc between any two nodesso nodes 8 and 9 are drawn and connected to node 10 via dummyarcs 35Copyright 2008, Dr. Steven A. GabrielFinding the Critical Path in an AOA ProjectNetwork for Introducing a New ation(Days)aTrain workers-6bPurchase raw materials-9cProduce product 1a,b8dProduce product 2a,b7eTest product 2d10fAssemble products 1 and 2into new product 3c,e12a1fc356debdummy arc2436Copyright 2008, Dr. Steven A. Gabriel18
Finding the Critical Path in an AOAProject Network for Introducing a NewProductmin x6-x1s.t.x3-x1 6 ! arc (1,3)Why variables free (i.e., notx2-x1 9 ! arc (1,2)necessarily nonnegative)?x5-x3 8 ! arc (3,5)x4-x3 7 ! arc (3,4)When ok, when not?x5-x4 10 ! arc (4,5)x6-x5 12 ! arc (5,6)Excel version of thisx3-x2 0 ! arc (2,3)endLP?! could have variables free or not!free x1 x2 x3 x4 x5 x637Copyright 2008, Dr. Steven A. GabrielFinding the Critical Path in an AOAProject Network for Introducing a NewProductLP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION VALUE1)38.00000Í Project completed in 38 UCED COST0.0000000.000000Í LP will have many alternate optima all with 380.000000days. In general, the value of xi in an optimal0.0000000.000000solution may assume any value between ET(i) and0.000000LT(i).SLACK OR SURPLUS DUAL PRICES3.0000000.0000000.000000-1.000000Í Critical path goes from start to finish node in9.0000000.000000whicheach arc corresponds to a constraint with “dual0.000000-1.0000000.000000-1.000000price” -1, i.e., 1-2-3-4-5-6 is a CP (more on dual0.000000-1.000000prices later.)0.000000-1.00000038Copyright 2008, Dr. Steven A. Gabriel19
Finding the Critical Path in an AOAProject Network for Introducing a NewProduct For each constraint with a “dual price” of –1, increasing theduration of the activity corresponding to that constraint by deltadays will increase the duration of the project by delta days This assumes that the current vertex remains optimal Now we consider a time-cost tradeoff approach to scheduling39Copyright 2008, Dr. Steven A. GabrielProject Crashing inActivity on Arc (AOA)Project Networks40Copyright 2008, Dr. Steven A. Gabriel20
Project Crashing and Time-CostAnalysis, Sample DataProjectDurationCrashingStrategyDescription of CrashingTotalCostT 11S1Activities at normal duration 2,775T 10S2Crash F by 1 unit 2,800T 10S3Crash C by 1 unit 3,025T 10S4Crash E by 1 unit 2,875T 9S5Crash F and C by 1 unit 3,050T 9S6Crash F and E by 1 unit 2,900T 9S7T 9T 8 If c “crashable”activities, there are2c possible crashstrategies, why? Suppose we can crash6 of the 7 activitiesÎ26 64 possible crashstrategiesCrash C and E by 1 unit 3,125S8Crash E by 2 units 2,975 S9Crash F, C, and E by 1 unit 3,150There are 12 of the 64strategies shown hereT 8S10Crash F by 1 unit, E by 2 units 3,000T 8S11Crash C by 1 unit, E by 2 units 3,225T 7S12Crash F and C by 1 unit, and E by2 units 3,50041Copyright 2008, Dr. Steven A. GabrielProject Crashing and TimeCost Analysis42Copyright 2008, Dr. Steven A. Gabriel21
Project Crashing and Time-CostAnalysis –A Specific Example Define the variables:A # of days by which activity a is reduced (unit cost 10)B # of days by which activity b is reduced (unit cost 20)C # of days by which activity c is reduced (unit cost 3)D # of days by which activity d is reduced (unit cost 30)E # of days by which activity e is reduced (unit cost 40)F # of days by which activity f is reduced (unit cost 50) We have the following LP43Copyright 2008, Dr. Steven A. GabrielProject Crashing and Time-CostAnalysis -An Examplemin 10A 20B 3C 30D 40E 50Fs.t.A 5B 5C 5D 5E 5F 5x3-x1 A 6 ! arc (1,3)x2-x1 B 9 ! arc (1,2)x5-x3 C 8 ! arc (3,5)x4-x3 D 7 ! arc (3,4)x5-x4 E 10 ! arc (4,5)x6-x5 F 12 ! arc (5,6)x3-x2 0! arc (2,3)x6-x1 25 ! at most 25 daysend! could have variables free or not!free x1 x2 x3 x4 x5 x6Excel version of this LP?44Copyright 2008, Dr. Steven A. Gabriel22
Project Crashing and Time-CostAnalysis -An Example9026c3a1f5386debdummy arc249164013c3a1f5ebdummy arc244256d645Copyright 2008, Dr. Steven A. GabrielNormal AOA networkTotal project time 38 daysCP 1-2-3-4-5-6Numbers by nodes are solutionCrashed AOA networkTotal cost 390Total project time 25 daysCPs 1-2-3-4-5-6, 1-3-4-5-6Numbers by nodes are solutionCrash variables:A 2,B 5,C 0,D 5,E 3,F 0Precedence DiagrammingMethod inActivity on Arc (AOA)Project Networks46Copyright 2008, Dr. Steven A. Gabriel23
Precedence Diagramming Method(PDM) Normal CPM assumptions are that a task B cannot start untilits predecessor task A is completely finished PDM allows activities that are mutually dependent to beperformed partially in parallel instead of serially The usual finish-to-start dependencies are “relaxed” so thatthe performance of the activities can be overlapped The result is that the project schedule can be compressed (likeproject crashing in that sense)47Copyright 2008, Dr. Steven A. GabrielPrecedence DiagrammingMethod (PDM) 1.The time between the finishing or starting time of the 1stactivity and the finishing or starting time of the 2nd activity iscalled the lead-lag requirement between the two activitiesFour basic lead-lag relationships to consider:Start-to-Start Lead (SSAB) This specifies that activity Bcannot start until activity A has been in progress for at least SStime unitsSSExample?AB48Copyright 2008, Dr. Steven A. Gabriel24
Precedence DiagrammingMethod (PDM)2.Finish-to-Finish Lead (FFAB) This specifies that activity Bcannot finish until at least FF time units after the completion ofactivity AExample?ABFF49Copyright 2008, Dr. Steven A. GabrielPrecedence DiagrammingMethod (PDM)3.Finish-to-Start Lead (FSAB) This specifies that activity Bcannot start until at least FS time units after the completion ofactivity A (CPM takes FSAB 0)Example?ABFS50Copyright 2008, Dr. Steven A. Gabriel25
Precedence DiagrammingMethod (PDM)4.Start-to-Finish Lead (SFAB) This specifies that there must beat least SF time units between the start of activity A and thecompletion of activity BExample?ASFB Can also express the leads or lags in percentages (instead oftime units)Can also use “at most” relationships as well as the “at least”ones shown above 51Copyright 2008, Dr. Steven A. GabrielPrecedence DiagrammingMethod (PDM) An example: 3 activities done in seriesÎ project duration of 30 days using conventional CPM 1015 20 25 30 35 40 45 50Days52Copyright 2008, Dr. Steven A. Gabriel26
Precedence DiagrammingMethod (PDM) The same 3 activities done in series but with lead-lag constraintsÎ project duration of 14 days, a 16 day speedup over theconventional CPM method0,102,124,14A,10B,10C,102,124,14SS(BC) 2FF(BC) 20,10SS(AB) 2FF(AB) 2CBA24101214Days53Copyright 2008, Dr. Steven A. GabrielPrecedence DiagrammingMethod (PDM) Must be careful about possible anomalies in PDMExample:0,10A,100,10 10,2020,30B,10FF(AB) 10,20 10C,10SS(BC) 20,30 10Now crash B and reduce the duration of task B from 10 days to5 daysYou would think that the total projection duration woulddecrease from 30 to something lowerHowever, the SS(BC) constraint forces the starting time of C tobe shifted forward by 5 daysÎ project duration actuallyincreases even though B’s duration has decreased!54Copyright 2008, Dr. Steven A. Gabriel27
Precedence DiagrammingMethod (PDM)FF(AB) 10A010BBefore B’s time is reduced20C30SS(BC) 10FF(AB) 10A010B1520C2535SS(BC) 10After B’s time is reducedAs a safeguard, may want toperform one activity changeat a time and record theresult55Copyright 2008, Dr. Steven A. GabrielPrecedence DiagrammingMethod ExampleYou are a planner at the National Aeronautics and Space Administration(NASA) planning the next major rocket development, production, andlaunching to the planet Neptune. Due to the particular positioning of the planetNeptune relative to Earth and the other planets in between, the rocket must bewithin 100,000 kilometers of the planet Saturn somewhere between 120 and125 months from today in order to make it to Neptune in a reasonable amountof time.If this time window is not satisfied, the cost of reaching Neptune skyrocketsdramatically (no pun intended). For example, if the time is greater than 125months, it is estimated that 100 million more are needed to reach Neptune dueto additional engineering considerations. Consider the following set ofactivities related to this project shown in the following table.56Copyright 2008, Dr. Steven A. Gabriel28
PDM-AOA Project Network velop trajectoryplan for rocketGeneratespecifications forrocket designRequest funding fromCongressBegin initial searchfor contractorsPrepare modifiedbudget (usingsuggestions fromCongress)Select rocketcontractorBuild and test rocketCreate simulationmodel for rockettrajectoryPrepare rocket launch& launch rocketProceed towardsJupiter and thenperform gravitational“slingshot” maneuveraround JupiterAchieve Saturn orbit(within 100,000kilometers)ImmediatePredecessors-Duration ,24E,128G,4879FFdummy arc4824precedence arcG,H12I36J1I,1210J,3611K,11257Copyright 2008, Dr. Steven A. GabrielPDM-Example Compute the critical paths and project duration by formulating and solving an appropriateLP model to capture the precedence relationships between the activities. Let xi be the timefor node i. The associated LP model is thus:min x12-x1s.t.A) x2-x1 5 ! A1 A,5B) x3-x2 12 ! B2 B,12C) x4-x3 12 ! CD,6F,1235D) x5-x3 6 ! DC,126 H,24E) x5-x4 12 ! E4 E,128G,48F) x6-x5 12 ! F7G) x7-x6 48 ! G9H) x8-x6 24 ! HI,1210DU1)x9-x8 0 ! dummy arc dummy arcJ,36 11DU2)x9-x7 0 ! dummy arc precedence arcI) x10-x9 12 ! IK,112J) x11-x10 36 ! JK) x12-x11 1 ! K58Copyright 2008, Dr. Steven A. Gabriel29
PDM-Example1OBJECTIVE FUNCTION 9.000000SLACK OR 000000.000000REDUCED DUAL ummy arcprecedence arcI,1210J,36critical path arc11K,112We see that the project time is 150 monthswhich is too high (greater than 125 months).59Copyright 2008, Dr. Steven A. GabrielPDM-ExampleQuestion:Due to various reasons, it is believed that activities A, B, C, andD can be sped up as follows. Activity B can start as soon as 1month after A starts. Activity C can start as soon as 1 monthafter activity B starts. Activity D can start as soon as one monthafter activity C starts. The total cost for this acceleration is 5,000,000. Modify the project network from part a (i.e., theuncrashed one) to allow for these possibilities. What is the totalproject time allowing for these changes?Note: Could also try project crashing to speed things up, notconsidered here.60Copyright 2008, Dr. Steven A. Gabriel30
PDM Combined with LP Create one start and one end node for eachactivity that has a PDM rule. Insert arrows to enforce the newrelationships Solve as previous cases61Copyright 2008, Dr. Steven A. GabrielPDM-ExampleAnswer:We can modify the AOA network to include two nodes for A, namely A1 and A2 when activity Astarts and when it finishes, respectively. The same modification can be applied to activities B, C, andD. We need to make sure that the earliest that B1 can start is 1 month after A1, the earliest that C1 canstart is 1 month after B1, and the earliest that D1 can start is 1 month after C1. The resulting newproject network is as follows. Note: there is some arbitrariness in connecting A2, B2, and D2, otherA,5slight variations are possible.A1A2 1 1B1B,12B24C,12 1C1C25F,96G,38D,6D1E,12H,24879D2I,12dummy arcprecedence arciJ,3611K,1ti621012ti time that node i is visitedCopyright 2008, Dr. Steven A. Gabriel31
PDM-ExampleNew model is thus:min x12-xa1s.t.A) xa2-xa1 5 !B) xb2-xb1 12 !C) xc2-xc1 12 !D) xd2-xd1 6 !A,5A1A2 1 1B1B,12B24C,12 1C1C2D1E,125F,96G,38D,6H,24879D2I,12dummy arcSS1)xb1-xa1 SS2)xc1-xb1 SS3)xd1-xc1 111! SS(A,B) 1! SS(B,C) 1! SS(C,D) 1A2)B2)C2)D2)xb2-xa2 xc2-xb2 x4 -xc2 x5 -xd2 0000!!!!A2B2C2D2E) x5 -x4 F) x6 -x5 G) x7 -x6 H) x8 -x6 DU1) x9 -x8 DU2) x9 -x7 I) x10-x9 J) x11-x10 K) x12-x11 121248240012361!!!!!!!!!EFGHdummy arcdummy arcIJKbeforebeforebeforebeforeB2C24510precedence arcJ,3611K,1tiiABCD12ti time that node i is visited63Copyright 2008, Dr. Steven A. GabrielPDM-ExampleOBJECTIVE FUNCTION 00086.00000098.000000134.000000REDUCED 0.0000000.0000000.0000000.0000000.000000SLACK OR 0000.0000000.000000DUAL -1.000000-1.000000-1.000000Total project time is 135 months, still too big, will need to consider crashing the project.64Copyright 2008, Dr. Steven A. Gabriel32
PDM ExampleA,5A1OBJECTIVE FUNCTION VALUEA21) 1 1B1B,12B24C,12 1C1C25F,96G,38D,6D1E,12H,24879D2I,12dummy arcprecedence 1X4X5X6X7X8X9K,1X10X11ti time that node i is 0098.000000134.000000REDUCED t 2008, Dr. Steven A. GabrielInteger Programming All linear programming problems so far assumed that fractionalanswers were acceptable– In practice not always ok, why?– Certain classes of LPs we studied will have integer solutions,which ones and why? Want to explore modeling aspects when we specify certainvariables must be integer-valued– Why this is a MUCH harder problem to solve in general– Interesting applications of binary variables for encoding logic inmathematical programs66Copyright 2008, Dr. Steven A. Gabriel33
The Toy ProblemRevisited67Copyright 2008, Dr. Steven A. GabrielThe Toy Problem RevisitedRecall the toy production problem from before Complete LPMax 3x1 2x2s.t.2x1 x2 100x1 x2 80x1 40x1 0x2 0(Objective function)(Finishing constraint)(Carpentry constraint)(Limited demand constraint on soldiers)(Nonnegativity constraint on soldiers)(Nonnegativity constraint on cars)Optimal solution: x1 20, x2 60 , with an optimal objective function value of z 18068Copyright 2008, Dr. Steven A. Gabriel34
The Toy Problem Revisited According to LP theory, a solution (if itexists) must be at one of the vertices(also called extreme points)LPfeasibleregion (0,0) (0,80) (20,60) (40,20) (40,0) In this case, all vertices are integer-valued (i.e., whole numbers)This is fortunate since we want to produce a whole number of toys andsoldiersWhat if this were not the case? That is, what if the the solution were notinteger-valued?69Copyright 2008, Dr. Steven A. GabrielThe Toy Problem Revisited Modified Complete LPMax 3x1 2x2(Objective function)s.t.2x1 x2 99.7(Finishing constraint)x1 x2 83.5(Carpentry constraint)x1 40(Limited demand constraint
Note, Gantt chart shows for example: Starting time of F can be delayed until day 7 (TS 5) w/o delaying overall project Also, A, D, or both may be delayed by a combined total of four days (TS 4) w/o . The early event time for node i, ET(i), is the earliest time at which the event
Class- VI-CBSE-Mathematics Knowing Our Numbers Practice more on Knowing Our Numbers Page - 4 www.embibe.com Total tickets sold ̅ ̅ ̅̅̅7̅̅,707̅̅̅̅̅ ̅ Therefore, 7,707 tickets were sold on all the four days. 2. Shekhar is a famous cricket player. He has so far scored 6980 runs in test matches.
New York Buffalo 14210 New York Buffalo 14211 New York Buffalo 14212 New York Buffalo 14215 New York Buffalo 14217 New York Buffalo 14218 New York Buffalo 14222 New York Buffalo 14227 New York Burlington Flats 13315 New York Calcium 13616 New York Canajoharie 13317 New York Canaseraga 14822 New York Candor 13743 New York Cape Vincent 13618 New York Carthage 13619 New York Castleton 12033 New .
New Holland T4020-T4050 New Holland T4030F-T4050F New Holland T4030V-T4050V New Holland T4.75-T4.100 New Holland T5040-T5070 New Holland TD5050 New Holland T6010-T6090 New Holland T7.170-T7.270 New Holland TT45A-TT75A New Holland TN55-TN75 New Holland TN60A-TN95A New Holland TN55D-TN75D New Holland TN60DA-TN95DA
New Holland T4020-T4050 New Holland T4030F-T4050F New Holland T4030V-T4050V New Holland T4.75-T4.100 New Holland T5040-T5070 New Holland TD5050 New Holland T6010-T6090 New Holland T7.170-T7.270 New Holland TT45A-TT75A New Holland TN55-TN75 New Holland TN60A-TN95A New Holland TN55D-TN75D New Holland TN60DA-TN95DA
MM J. H. Moulton and G. Milligan, The Vocabulary of the Greek New Testament MT Massoretic Text NA Nestle-Aland Greek New Testament (27th ed.) NAB New American Bible NEB New English Bible NIDNTT New International Dictionary of New Testament Theology NIV New International Version NJB New Jerusalem Bible NLT New Living Translation NovT Novum .
living collection living prestige l 375 garlic oak new new vision oxid hydro 1183x396x8 mm / 1184x601x8 mm new new new facile 1288x198x8 mm new new newnew new new new
New York State; and 4. The vehicle is primarily for personal use. Some examples of cars that may be covered by the new car lemon law are: ! a new or demonstrator car, purchased or leased from a New Jersey dealer and registered in New York;! a new or demonstrator car, purchased or leased from a New York dealer and registered in New Jersey;
Calligraphy Learn how to write beautifully and develop your creativity with calligraphy. You will learn fundamental approaches, letterforms, layout and design. Calligraphy can be used to enhance artwork, illustrate writing, create invitations or as a stand-alone art form. Calligraphy - beginners and progression to intermediate
