Linear programming

Introduction

Project managers often find themselves in situations where it is necessary to determine the level at which to operate each activity or identifiable sub-part of a project. Each activity in turn has necessary prerequisite activities which must be completed prior to starting it. Thus results the familiar network configuration with the likelihood of several of these activities being preformed simultaneously.

In a simplified sense each of the activities can be run at what is referred to as its “normal” time or its “crash” time. The normal time is defined as that duration of an activity that results in the smallest cost when only that particular activity in itself is performed. The crashing of an activity results in expediting the effort so that it takes less time but is higher in cost. When project overhead costs are included it may be financially advantageous to run several of the activities at crash levels providing that doing so reduces the total project duration and the corresponding overhead costs. In essence, then, the problem is to balance the increased costs of crashing activities with the reduction in total overhead costs.

Although the problem seems simple enough, most project managers are aware of severe complexities. The key problem is associated with the project duration, not the activity duration. If a particular activity is not on the critical, or longest path, then a reduction in that activity’s duration will not reduce the project duration and consequently is of no avail. Further, even crashing an activity on the critical path may be advantageous if it is crashed to such an extent that a sub-critical or parallel path becomes the critical path. It may be advantageous to simultaneously crash several activities on different, but parallel paths if the costs are justified. The complexities of determining an overall crashing strategy become overwhelming when realistically sized problems of several hundred or even thousands of activities are considered.

The purpose of this paper is to demonstrate how such a problem can be formulated with relative ease into a linear programming model for use on most computers with a linear programming package. It will further be shown that a major advantage of such a model is the opportunity it provides to control the project during the implementation stage.

THE BASIC LINEAR PROGRAMMING MODEL

The model itself contains two classes of variables. First there are the variables associated with the activities, which define how long it should take to perform an activity. Secondly, the variables associated with event times determine in which day each of the events should take place. As expected there are also two classes of restrictions: those restricting the duration of the activities to a value between the crash time and the normal time, and those defining the network configuration. The linear programming model can quite properly be classified as a “time variable model.” This means that certain items must be performed in some prearranged sequence, where the only variable that is unknown is the time when such items are to occur. The early work in this “time-variable” model formulation was published by Fulkerson in Management Science,¹ and by Kelley in Operations Research.² Practical applications of this approach, however, have been limited, possibly due to the highly quantitative and somewhat confined approach of these early papers.

The approach that is taken can best be described as viewing the problem in a reverse sense. The model actually starts with all activities at their crash level, and then proceeds to “uncrash” these activities until total costs are at a minimum. Consider the following activity that has a normal level and a crash level with times designated as N and C. D^c and Dⁿ represent the cost in dollars respectively. The point designated D^t, the theoretical dollar cost if the activity could be run at zero time, is found by extending the cost slope until it intersects the vertical axis. It is this point that is used as an initial starting point for the activities. Restrictions are added to insure that the activity takes at least as much time as C (the crash time), and no more that N (the normal time), thus insuring that the activity is performed at some feasible level.

Figure 1 - Activity Times and Dollar Costs

Key: C = crash time, N = Normal time

In essence this theoretical dollar crashing cost is considered a fixed cost, and the distance that is moved down the slope is a reduction in this cost. The reduction in this dollar cost can easily be determined by multiplying the time of the activity, A, by the obsolute value of the slope, S, where the slope, is defined as

Thus the cost for a particular activity performed at a level A would be

For an entire project the total direct cost for all A_ij activities would be

Since the sum of the theoretical dollar crash costs, , is a fixed amount, the only way to reduce the total direct cost is to increase the amount of Hence the objective is to

which, when subtracted from the theoretical crash costs, will minimize the total direct cost.

As mentioned earlier, the restrictions are of two classes. First consider the more straightforward of the two, the activity restrictions. Each activity duration, A_ij, must be greater than or equal to the crash time, C_ij.

Similarly, each activity must also operate at a level less-than-or-equal-to the normal time.

These restrictions insure that the activity will be performed within the designated range.

To incorporate the second class of restriction, the network prerequisites, it is necessary to introduce the event times, E. Quite simply, the restriction can be stated as follows: the time of the starting event, E_i, plus the duration of the activity, A_ij, must be equal to or less than the time of the ending event, E_j.

Transposing the variable E_j to the left side as per linear programming convention, (7) becomes

The less-than-or-equal sign actually allows for any possible float time. If the restriction were stated as strictly an equality, then no float time could exist. This could cause the network to be infeasible, or could unduly increase the costs of the overall project. Naturally those activities on the critical path will not contain any float time and in this cost equation (8) will effectively be an equality, but the critical path will be determined by the linear programming solution.

Actually the E_i variables serve principally as a bookkeeping function and only the final event has an impact on the objective function. The time of the final event constitutes the completion date of the project and, since the project can be assumed to start on day zero, the time for the last event also constitutes the duration of the project. Thus the earlier events serve in a bookkeeping capacity by summing the activity times according to the particular network configuration to yield the duration of the project.

Exactly how this information about the completion or duration of the project is used depends upon the particular problem at hand. For instance, if the problem is to minimize the costs of performing the activities subject to completing the project by at least some specified time, then one or restriction would be added as follows:

where E_L represents the last event time and T is the specified completion time.

If, on the other hand, rather than specifying a completion date a daily overhead cost is present for each day of the project, the problem would then be to minimize the sum of the direct activity expense plus the overhead cost. In this instance (9) would be eliminated and the objective function in (4) would be modified to

where O represents the daily overhead expense. The term OE_L is subtracted because the objective function is stated as a maximization and OE_L is an expense item.

If, however, the problem is to minimize the total of direct activity, overhead, and penalty costs, then further modifications must be made. Such a situation frequently occurs when a contract specifies a completion date after which a daily penalty is incurred. The inclusion of such a daily penalty is accomplished by the addition of a single variable and an additional restriction. If p represents the daily penalty cost and q represents the quality or number of days that the penalty would occur, then the objective function would be revised to

Again, since the objective is to maximize, the total penalty cost pq is considered as an expense item and would have to be subtracted. The additional restriction would be of the form

where E_L is again the last event time and T_p would be the date or time when a daily penalty would begin to be charged. As can be seen, E_L could be increased up to T_p before any penalty would be assessed.

Several modifications can be made in the model to accommodate certain forms of overhead expenses. For instance if some form of additional overhead resulted during the time between two events, say E_x and E_y, then the objective function would become

and the restriction

is added. Here, O_A refers to the daily additional overhead and R represents the required number of days this additional overhead is charged. Naturally, several types of additional overhead may be included to estimate a varying overhead condition dependent on the type and nature of activities.

It should be apparent there is a considerable amount of flexibility in the manner in which an overhead or a completion date can be included in the model. There is also considerable flexibility in the manner in which the activities can be formulated. For instance, consider the situation in which there exists a second crash level in addition to the first crash and the normal level (figure 2).

Figure 2 – Activity With Two Crash Levels

In this instance there are two cost slopes, S¹ and S², for the first and second crash respectively. This necessitates dividing the activity into two parts, A¹ and A² which alters the basic network restrictions of (8) to

The objective function becomes

The restrictions about the activities then become

These restrictions will hold only if the slope of the second crash is greater than the slope of the first crash. This is because it is necessary to “un-crash” the second crash before “un-crashing” the first crash. With a maximizing objective function the variable with the largest coefficient in the objective, all other things being equal, will be brought into solution first. If the slope of the first crash had the unusual distinction of being larger than the slope of the second crash, then it is possible that the solution would call for “un-crashing” the first crash but not the second. This is, of course, not very meaningful. If such a rare reverse slope does occur, the best way to handle the problem is to treat the activity as a single crash, with the slope time running straight from the normal to the second crash.

If on the other hand an activity could only be operated at a single (for example, the maximal) level, then it is not considered a variable and there would be no activity restrictions. The network restriction would be written as

or transposing,

where N_ij is the normal time. Dummy activities would be treated in a similar manner, with the time being zero.

Sometimes it may be advantageous to force some amount of float into a particular path to allow for contingencies. This is easily accomplished by making a small alteration in the basic network restrictions of (8) to

where F_ij is the amount of float desired between the i^th and j^th events. The negative sign on the right hand side forces E_j, the ending event, on the left side to be greater than the starting event, E_i, plus the activity duration and thus creates or insures float.

A NUMERICAL EXAMPLE

In an effort to consolidate most of the elements of the previously developed model a small example is formulated into linear programming form. Consider for the moment the network in figure 3 consisting of seven activities, plus two dummy activities indicated by the dashed arrows. The costs for the various crashing levels is given in Table 1.

To formulate the problem in the linear programming framework, it is first necessary to compute the cost slopes for the respective crash levels by employing equation (1). The results of these computations are given in Table 2.

These cost slopes then become the coefficients for their respective activities in the objective function. (It should be noted that if any of the second crash cost slopes were smaller than the first crash cost slopes, then the activity would have to be approximated by ignoring the first crash and assuming a straight line from normal to second crash.) Now assuming an overhead cost of $70 per day, the complete objective function as given by equation (16) can be formulated and written in simplex table form (Figure 4) as row 0. Note that, except for the last one, none of the events have any direct effect on the objective function. They thus have zero for coefficients in the formulation.

The activity restriction as shown by rows 1 through 18 are formulated by employing equations (5) and (6) for those activities with only a single crash level (A₁₂, A₂₄, and A₆₇) while equations (17), (18) and (19) are used for the activities with two crash levels. For instance, A₁₂ has two restrictions, row 1 and 2. These state that the duration must be greater-than-or-equal-to 7, the crash time, and less-than-or-equal-to 9, the normal time. On the other hand, activity A₁₃, which has a second crash, must be broken into two components. The second crash A₁₃ must be greater-than-or-equal-to 5, the second crash time, and less-than-or-equal-to 7, the first crash (rows 4 and 5). The first crash A₁₃ must be less-than-or-equal-to 1 (Row 3), the difference between the normal and first crash times.

Figure 3 - Sample CPM Network Configuration

Table 1 - Direct Activity Costs

*Note: It is assumed that activities A₁₂, A₂₄, and A₆₇ cannot be crashed at the second level.

*Note: These activities cannot be crashed at the second level.

Table 2 – Cost Slope

The network restrictions, rows 19 through 26, utilized either equation (8) or (15) depending on whether the activity had one or two crashes respectively.

It should be noted how the two dummy activities impact the formulation. The real purpose of dummy activity A₄₆ was to improve the appearacne of the networks. That is, convention dictates that activity arrows should be straight, not curved. This linear programming model requires no such convention, however, so the restriction for activity A₂₄ is written as if the activity actually went from event 2 directly to event 6. With the second dummy, such is not the case. This activity serves in the capacity of specifying necessary prerequisites. Hence this restriction must be included in the model as row 25 in figure 5.

Solving the resulting linear programming problem will yeild values for the variables as shown in Table 3. To find the activity durations for those activities with a second crash it is necessary to combine the duration of the two crash levels.

The event time for the last event E₇, gives the duration for the entire project, 19 days in this case. The time for the other events may or may not be of interest depending upon the individual user. The total cost of the project can be determined either by computing the som of the individual theoretical cost levels (D_ij^t) and subtracting the value of the objective function, or by summing up the direct activity costs from the levels determined by the linear programming solution and adding the total overhead cost.

CONTROLLING THE PROJECT

To this point linear programming has been presented as a useful managerial planning tool for a CPM type of project. Once the project has been started, however, one need not continue with the same plan throughout the entire project. The same linear programming model can aid in project control with only slight modifications to take account of the actual durations of activities that have been completed.

To gain the proper prospective it is convenient to view the project as a series of stages where at each stage several of the activities are performed. Naturally the decision as to the extent of crashing for each of these activities depends on the immediate period and also on all of the remaining periods. However, once some of these activities have been performed and have deviated from the expected schedule, the original problem and its solution has been altered. Depending upon the amount of deviation it may very well be that the remaining crashing strategy is no longer optimal.

To find the new strategy it is necessary to resolve the problem with the completed activities defined not as variables, but as fixed values determined by their actual durations. Only the first few activities are actually performed from the new solution, but all of the remaining activities are considered in determining the new crashing strategy. When information is at hand concerning the actual duration of the (new) initial activities, then the newly revised problem is again resolved. This process continues until the project has been completed.

In essence, an optimal crashing strategy is continually being determined when information becomes available concerning the actual project. Determining such crashing strategies is not something that one relishes if it is to be done by hand. The linear program, however, accomplishes this with relative ease. To illustrate this point, consider the previous example. Assume for the moment that during the first 10 days of the project that the information given in Table 4 has been made available.

Table 4 - Hypothetical Current Project Status

There are several means available for including this information in the model. One way would be to reformulate the model eliminating these three activities as variables and fixing the duration between the events as designed in Table 4. However, once the basic model has been established it is easier to merely alter the right hand side to fix the duration of the activities. In this instance the following changes would be made:

These changes involve only the right hand side values and are relatively simple to make. It should be noted that although activity A₃₅ has not been completed it is not a variable, i.e., it is assumed that the crash level can not be altered at this time, and as such the best and most current information concerning its duration is included. Sometimes it may be necessary to include certain activities at fixed levels that have not been started, but due to previous committed planning factors that can now not be altered from their planned levels.

Controlling a project in this manner allows the project manager to take advantage of any changes that may occur from the planned to the actual activity durations. Naturally the more frequently one up-dates the project the lower the project costs should be; however this improvement increases at a decreasing rate. There are of course costs for collecting this actual information and for running the program which must be balanced with this recuced cost.

LIMITATIONS AND CONCLUSIONS

One of the major assumptions in linear programming models is that of continuity. In this model it has been assumed or implied that any point along the cost slope from the normal level to the crash level is feasible. Certainly this is not always the case, but that does not invalidate the model. In most instances the solution will yield activity durations that will be at the extremes, i.e., either at the normal or the crash level. In fact, there will be at most one activity per loop or path that will not be at such a point.

Figure 4 - Initial Simplex Table for Sample Problem

This particular problem can be solved. However, this requires that integer constraints be included. For instance, if an activity could only be operated at its normal or crash level, designated as A_ijⁿ and A_ij^c , the following restrictions would be employed:

where I_ij, is an integer value of either 0 or 1 and N_ij and C_ij are the normal and crash times. The coefficients in the objective function for A_ijⁿ and A_ij^c, correspond to the total reduction in cost from the theoretical dollar cost, D_ij^t.

The inclusion of the integer constraints requires the use of a mixed integer programming package which slows down the solution procedures considerably. Unfortunately the integer programming algorithms available today are not capable of handling cufficiently large numbers of integer variables to make their use practical for large projects. However since there are relatively few activities that will be found in solution that call for operation between crash levels [the numerical example had to be especially designed so that two activities (A₂₆ and A₅₇) fall into this category.] not a great amount of accuracy is lost by rounding these activities to their nearest level.

Another limitation is that of the assumption of certainty. Linear programming treats all coefficients as facts. Of particular concern are the durations of the activities. Since the estimates are treated with certainty there is no value for any float time, so the solution contains little. This is readily apparent by viewing the time-activity diagram³ of the numerical example in Figure 5. This possibly undesirable feature can be alleviated by forcing some fixed amount of float time into the non-critical paths via equation (21) before attempting to crash or even possibly by including the floatias a segmented variable with increasing associated costs. Naturally as the uncertainty is reduced, for instance as the project proceeds and the length of the uncompleted portion is reduced, then the forced float time should also be reduced.

Figure 5 — Time Activity Diagram of the Linear Programming Solution

Even with these limitations the judicious use of linear programming for CPM type problems has a number of advantages. One need not have to write a computer program to solve a linear programming problem as most computer installations already have such programs available or can readily obtain them. In fact, most such programs have been developed to the extent that projects containing over a thousand activities are easily solvable. In addition, the relatively simple model structure used here, containing only two classes of variables (activities and events) and restrictions (activity and network) allows the model to be readily formulated. It is a relatively simple matter to write a computer program to generate the entire matrix from a list of activities, times, and costs such as given by Table 1 (such programs are commonly referred to as matrix generators).

The model has a considerable amount of flexibility and can be applied to most any CPM type of project, especially those with varying amounts of overhead, project deadlines, or possible delay penalties. In fact the model can also be formulated to include several projects simultaneously.