IE 413 Engineering OR I Homework #5 Due Thursday, November 12, 2015

stroke-width: 0px; ">Part I: Transportation Problem
Las Cruces Academy can store 200 files on hard drive, 100 files in USB flash drive, and
300 files on DVD. Users want to store 300 word-processing files, 100 packaged-program
files, and 100 data files. Each month a typical word-processing file is accessed nine times;
a typical packaged-program file, five times; and a typical data file, three times. When a
file is accessed, the time it takes for the file to be retrieved depends on the type of file and
on the storage medium (see table below).
Storage Medium Time (Minutes)
Word Processing Packaged Program Data
Hard Drive 5 4 7
USB Flash Drive 3 2 1
DVD 10 8 5
If the goal is to minimize the total time per month that users spend accessing their files,
determine the linear programming model formulation that can be used to determine
where files should be stored (4 points).
Part II: Assignment Problem Consider the assignment problem having the following cost table: Task 1 2 3 4 Assignee A 8 7 5 7 B 6 5 3 4 C 7 8 4 6 D 6 6 5 6 a. Determine the linear programming model formulation to minimize the total assignment cost (2 points). b. Manually apply the Hungarian algorithm to find the optimal assignment (2 points).
Part III. Read the attached reading material (i.e., pages 413 – 417 of Hillier & Lieberman’s OR text, 10th edition), and write a one-page summary report. The summary
should be typed, double-spaced with 1" margins on all sides. Be concise in your writing and consult technical writing references as needed. The body of the summary report should include the sections outlined as follows: (1) Summary of the Chapter’s main point; (2) Your opinion of the Chapters including the most important information you learned
(2 points).
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
9. Network Optimization
Models
Text © The McGraw−Hill 407
Companies, 2010
9.8 A NETWORK MODEL 399
■ 9.8 A NETWORK MODEL FOR OPTIMIZING A PROJECT’S
TIME-COST TRADE-OFF
Networks provide a natural way of graphically displaying the flow of activities in a major
project, such as a construction project or a research-and-development project. Therefore,
one of the most important applications of network theory is in aiding the management of
such projects.
In the late 1950s, two network-based OR techniques—PERT (program evaluation
and review technique) and CPM (critical path method)—were developed independently
to assist project managers in carrying out their responsibilities. These techniques were designed to help plan how to coordinate a project’s various activities, develop a realistic
schedule for the project, and then monitor the progress of the project after it is under way.
Over the years, the better features of these two techniques have tended to be merged into
what is now commonly referred to as the PERT/CPM technique. This network approach
to project management continues to be widely used today.
One of the supplementary chapters on the book’s website, Chap. 22 (Project Management with PERT/CPM), provides a complete description of the various features of
PERT/CPM. We now will highlight one of these features for two reasons. First, it is a
network optimization model and so fits into the theme of the current chapter. Second, it
illustrates the kind of important applications that such models can have.
The feature we will highlight is referred to as the CPM method of time-cost tradeoffs because it was a key part of the original CPM technique. It addresses the following problem for a project that needs to be completed by a specific deadline. Suppose
that this deadline would not be met if all the activities are performed in the normal
manner, but that there are various ways of meeting the deadline by spending more
money to expedite some of the activities. What is the optimal plan for expediting
some activities so as to minimize the total cost of performing the project within the
deadline?
The general approach begins by using a network to display the various activities and
the order in which they need to be performed. An optimization model then is formulated
that can be solved by using either marginal analysis or linear programming. As with the
other network optimization models considered earlier in this chapter, the special structure
of the problem makes it relatively easy to solve efficiently.
This approach is illustrated below by using the same prototype example that is carried through Chap. 22.
A Prototype Example—the Reliable Construction Co. Problem
The RELIABLE CONSTRUCTION COMPANY has just made the winning bid of $5.4 million to construct a new plant for a major manufacturer. The manufacturer needs the plant to
go into operation within 40 weeks.
Reliable is assigning its best construction manager, David Perty, to this project to help
ensure that it stays on schedule. Mr. Perty will need to arrange for a number of crews to
perform the various construction activities at different times. Table 9.7 shows his list of
the various activities. The third column provides important additional information for coordinating the scheduling of the crews.
For any given activity, its immediate predecessors (as given in the third column of Table 9.7) are those activities that must be completed by no later than
the starting time of the given activity. (Similarly, the given activity is called an
immediate successor of each of its immediate predecessors.)
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
9. Network Optimization
Models
408 Text © The McGraw−Hill
Companies, 2010
400 CHAPTER 9 NETWORK OPTIMIZATION MODELS
■ TABLE 9.7 Activity list for the Reliable Construction Co. project
Immediate Estimated
Activity Activity Description Predecessors Duration
A Excavate — 2 weeks
B Lay the foundation A 4 weeks
C Put up the rough wall B 10 weeks
D Put up the roof C 6 weeks
E Install the exterior plumbing C 4 weeks
F Install the interior plumbing E 5 weeks
G Put up the exterior siding D 7 weeks
H Do the exterior painting E, G 9 weeks
I Do the electrical work C 7 weeks
J Put up the wallboard F, I 8 weeks
K Install the flooring J 4 weeks
L Do the interior painting J 5 weeks
M Install the exterior fixtures H 2 weeks
N Install the interior fixtures K, L 6 weeks
For example, the top entries in this column indicate that
1. Excavation does not need to wait for any other activities.
2. Excavation must be completed before starting to lay the foundation.
3. The foundation must be completely laid before starting to put up the rough wall, and
so on.
When a given activity has more than one immediate predecessor, all must be finished before the activity can begin.
In order to schedule the activities, Mr. Perty consults with each of the crew supervisors to develop an estimate of how long each activity should take when it is done in the
normal way. These estimates are given in the rightmost column of Table 9.7.
Adding up these times gives a grand total of 79 weeks, which is far beyond the deadline of 40 weeks for the project. Fortunately, some of the activities can be done in parallel, which substantially reduces the project completion time. We will see next how the
project can be displayed graphically to better visualize the flow of the activities and to
determine the total time required to complete the project if no delays occur.
We have seen in this chapter how valuable networks can be to represent and help analyze many kinds of problems. In much the same way, networks play a key role in dealing
with projects. They enable showing the relationships between the activities and succinctly
displaying the overall plan for the project. They also are helpful for analyzing the project.
Project Networks
A network used to represent a project is called a project network. A project network
consists of a number of nodes (typically shown as small circles or rectangles) and anumber of arcs (shown as arrows) that connect two different nodes.As Table 9.7 indicates, three types of information are needed to describe a project.1. Activity information: Break down the project into its individual activities (at the desired level of detail).2. Precedence relationships: Identify the immediate predecessor(s) for each activity.3. Time information: Estimate the duration of each activity.The project network should convey all this information. Two alternative types of projectnetworks are available for doing this.Hillier−Lieberman:Introduction to OperationsResearch, Ninth Edition9. Network OptimizationModelsText © The McGraw−Hill 409Companies, 2010One type is the activity-on-arc (AOA) project network, where each activity is representedby an arc. A node is used to separate an activity (an outgoing arc) from each of its immediate predecessors (an incoming arc). The sequencing of the arcs thereby shows the precedencerelationships between the activities.The second type is the activity-on-node (AON) project network, where each activityis represented by a node. Then the arcs are used just to show the precedence relationshipsthat exist between the activities. In particular, the node for each activity with immediatepredecessors has an arc coming in from each of these predecessors.The original versions of PERT and CPM used AOA project networks, so this was theconventional type for some years. However, AON project networks have some importantadvantages over AOA project networks for conveying the same information.1. AON project networks are considerably easier to construct than AOA project networks.2. AON project networks are easier to understand than AOA project networks for inexperienced users, including many managers.3. AON project networks are easier to revise than AOA project networks when there arechanges in the project.For these reasons, AON project networks have become increasingly popular with practitioners. It appears that they may become the standard format for project networks. Therefore, we will focus solely on AON project networks, and will drop the adjective AON.Figure 9.28 shows the project network for Reliable’s project.2 Referring also to thethird column of Table 9.7, note how there is an arc leading to each activity from each ofits immediate predecessors. Because activity A has no immediate predecessors, there isan arc leading from the start node to this activity. Similarly, since activities M and N haveno immediate successors, arcs lead from these activities to the finish node. Therefore, theproject network nicely displays at a glance all the precedence relationships between allthe activities (plus the start and finish of the project). Based on the rightmost column ofTable 9.7, the number next to the node for each activity then records the estimated duration (in weeks) of that activity.The Critical PathHow long should the project take? We noted earlier that summing the durations of all theactivities gives a grand total of 79 weeks. However, this isn’t the answer to the questionbecause some of the activities can be performed (roughly) simultaneously.What is relevant instead is the length of each path through the network.A path through a project network is one of the routes following the arcs fromthe START node to the FINISH node. The length of a path is the sum of the (estimated) durations of the activities on the path.The six paths through the project network in Fig. 9.28 are given in Table 9.8, along withthe calculations of the lengths of these paths. The path lengths range from 31 weeks upto 44 weeks for the longest path (the fourth one in the table).So given these path lengths, what should be the (estimated) project duration (the total time required for the project)? Let us reason it out.Since the activities on any given path must be done in sequence with no overlap, theproject duration cannot be shorter than the path length. However, the project duration canbe longer because some activity on the path with multiple immediate predecessors might9.8 A NETWORK MODEL 4012Although project networks often are drawn from left to right, we go from top to bottom to better fit on theprinted page.Hillier−Lieberman:Introduction to OperationsResearch, Ninth Edition9. Network OptimizationModels410 Text © The McGraw−HillCompanies, 2010have to wait longer for an immediate predecessor not on the path to finish than for theone on the path. For example, consider the second path in Table 9.8 and focus on activity H. This activity has two immediate predecessors, one (activity G) not on the path andone (activity E) that is. After activity C finishes, only 4 more weeks are required for activity E but 13 weeks will be needed for activity D and then activity G to finish. Therefore, the project duration must be considerably longer than the length of the second pathin the table.However, the project duration will not be longer than one particular path. This isthe longest path through the project network. The activities on this path can be performed sequentially without interruption. (Otherwise, this would not be the longest path.)402 CHAPTER 9 NETWORK OPTIMIZATION MODELS■ TABLE 9.8 The paths and path lengths through Reliable’s project networkPath LengthSTART ABCDGHM FINISH 2  4  10  6  7  9  2  6  40 weeksSTART ABCEHM FINISH 2  4  10  4  9  2  2  6  31 weeksSTART ABCEFJKN FINISH 2  4  10  4  5  8  4  6  43 weeksSTART ABCEFJLN FINISH 2  4  10  4  5  8  5  6  44 weeksSTART ABCIJKN FINISH 2  4  10  7  8  4  6  6  41 weeksSTART ABCIJLN FINISH 2  4  10  7  8  5  6  6  42 weeksA B C ED GHMKNLJFISTART 0FINISHA.B.C.D.E.F.G.H.I.J.K.L.M.N.Activity CodeExcavateFoundationRough wallRoofExterior plumbingInterior plumbingExterior sidingExterior paintingElectrical workWallboardFlooringInterior paintingExterior fixturesInterior fixtures2 4104 7585640296 7■ FIGURE 9.28The project network for theReliable Construction Co.project.Hillier−Lieberman:Introduction to OperationsResearch, Ninth Edition9. Network OptimizationModelsText © The McGraw−Hill 411Companies, 2010Therefore, the time required to reach the FINISH node equals the length of this path. Furthermore, all the shorter paths will reach the FINISH node no later than this.Here is the key conclusion.The (estimated) project duration equals the length of the longest path throughthe project network. This longest path is called the critical path.3 (If more thanone path tie for the longest, they all are critical paths.)Thus, for the Reliable Construction Co. project, we haveCritical path: START ABCEFJLN FINISH(Estimated) project duration  44 weeks.Therefore, if no delays occur, the total time required to complete the project should beabout 44 weeks. Furthermore, the activities on this critical path are the critical bottleneckactivities where any delays in their completion must be avoided to prevent delaying project completion. This is valuable information for Mr. Perty, since he now knows that heshould focus most of his attention on keeping these particular activities on schedule instriving to keep the overall project on schedule. Furthermore, to reduce the duration ofthe project (remember that the deadline for completion is 40 weeks), these are the mainactivities where changes should be made to reduce their durations.Mr. Perty now needs to determine specifically which activites should have their durations reduced, and by how much, in order to meet the deadline of 40 weeks in the leastexpensive way. He remembers that CPM provides an excellent procedure for investigating such time-cost trade-offs, so he will use this approach to address this question.We begin with some background.Time-Cost Trade-Offs for Individual ActivitiesThe first key concept for this approach is that of crashing.Crashing an activity refers to taking special costly measures to reduce the duration of an activity below its normal value. These special measures might include using overtime, hiring additional temporary help, using special time-saving materials,obtaining special equipment, etc. Crashing the project refers to crashing a number of activities in order to reduce the duration of the project below its normal value.The CPM method of time-cost trade-offs is concerned with determining how much(if any) to crash each of the activities in order to reduce the anticipated duration of theproject to a desired value.The data necessary for determining how much to crash a particular activity are givenby the time-cost graph for the activity. Figure 9.29 shows a typical time-cost graph. Notethe two key points on this graph labeled Normal and Crash.The normal point on the time-cost graph for an activity shows the time (duration) and cost of the activity when it is performed in the normal way. The crashpoint shows the time and cost when the activity is fully crashed, i.e., it is fullyexpedited with no cost spared to reduce its duration as much as possible. As anapproximation, CPM assumes that these times and costs can be reliably predictedwithout significant uncertainty.For most applications, it is assumed that partially crashing the activity at any level willgive a combination of time and cost that will lie somewhere on the line segment between9.8 A NETWORK MODEL 4033Although Table 9.8 illustrates how the enumeration of paths and path lengths can be used to find the criticalpath for small projects, Chap. 22 describes how PERT/CPM normally uses a considerably more efficient procedure to obtain a variety of useful information, including the critical path.