[MUSIC] In the previous module, we saw how we can reduce a project duration by incurring the least incremental cost of reducing the duration of activities on the critical parts. The meter is cumbersome and is not appropriate for large networks. In this module, we first showed how a linear programming approach can be used to calculate the earliest completion time of the project. This was calculated in an earlier module for the software project example using the forward pass through the network, then assuming a linear relationship between the duration of an activity and its direct cost. We extend the linear programming approach to find out the minimal incremental cost for each reduction in the project completion time from its normal completion time of 11 weeks, then we show how the meter can be adapted for finding out the project completion time. That gives the maximum net return consisting of the bonus for completing the project early minus the incremental direct cost of reducing the activity duration. In case, there's the reduction in indirect or overhead cost which is often the case and the project is completed early. This reduction in indirect cost will be added to the bonus of revenue generated by completing the project early. Finally, we show how the same linear programming approach can be modified to handle a certain type of nonlinear relationship between the duration of an activity and its static cost. To illustrate the use of linear programming approach to solve the problems mentioned above, we'll use the same software project example that we consider for crashing in the previous module. Recall that the project has eight activities with all the necessary data, such as normal duration, normal cost, crash time and crash cost are given in the table which is reproduced from the previous module. The precedence relationships are the same as in the previous module, which may also been far from the network diagram which is also reproduced from the previous module. A linear program consist of a linear objective function to be optimize that is maximized or minimized. Subject to linear equality and or inequality constraints. A function f(n) variable say, x1, x2 up to xn, is said to be linear. The function can be written as equal to a1 times x1 plus a2 times x2 and so on until we get to plus a and times xn plus b where a1, a2 to an and b are specified constants. To understand the formulation, we need to first define variables whose values are to be determined. So that, that data function is optimized while at the same time satisfying all the constraints. The first problem we'll consider is the variable Si denote the start time of activity i. Then for instance, SA would be denote the start time of activity A. Let T denote the completion time of the project. Now to find the values completion time of the project in this problem one, the constraints and the objective function and the linear programming formulas as shown in the table. The objective function is minimize t. In this formulation, we have two sets of constraints namely constraints on start times implied by the precedence relationships and non-negativity constraints. The constraint has to be greater than or equal to SA plus 2 states that the start time of activity B should be greater than or equal to the completion time of activity A, which is given by the start time of activity A plus its duration of two units. Similarly, we have the constraints for the other activities. Note that the two constraints SC greater than or equal to SB plus 4 and SC greater than or equal to SC plu 3, together imply that SC is greater than or equal to the maximum of SB plus 4, SB plus 3. Which in turn in place that the activity, it can be started only after both activities B and C have been completed as required by the precedence relationships. The objective function is to minimize the completion time of the project, denoted as T. There are two bids for denoting. First, the column constraints are shown on the right with all the variables on the left-hand side are then inequality or equality and the constant term on the right-hand side as required by many commercially available software. The second bind is that all the variables are required to be non-negative. In general, a solution to linear programming maybe such that some variables are fractional and not necessarily integer. Given that the duration of all activities are integers, we would want the start time of each activity and the project completion time to be integers. Fortunately, the structure of the constraints in the linear programming formulation above are such that an optimal solution will have integer values for all the variables. So, we don't have to explicitly introduce constraints stating that the variable should be integers. Solving the linear programming problem using the available software gives the project completion time TE equal to 11 and the start time of each activities. The second problem I'll consider, they would modify the above formulation to find out the minimal incremental cost for each specified project completion time. In addition to the variables, Si defined for each activity and variable T representing the project completion time. We define the following variables. Let Ri denote the reduction and the duration of activity from its normal duration. Then for instance, RB will denote the reduction and the duration of the activity B. Let alpha represent the reduction in the project completion time from its normal completion time of 11 weeks. The objective function is minimized 25 times RB plus 25 times RC plus 30 times RE. In this formulation, we have three sets of constraints. Namely, constraints implied by the precedence relationships. Upper bounds constrains on the reduction in activity durations and non-negativity constraints. Several variables, RA, RD, RF, RG and RH are set to zero since no reduction is possible in the duration of activities A, D, F, G and H respectively. These variables can be omitted from the formulation, but we have written them for illustration. The constraint is bigger than or equal to SA+(2-RA) states that the start time of activity B should be greater than of equal to the completion time of activity A, which is given by the start time of activity A plus its duration of 2 minus RA units of time representing the duration of activity A after a reduction of RA units of time. Similarly, we have constraints for other activities. Given that the duration and the maximum reduction in the duration of activities are integers, the structure of the constraints in this formulation also as in the case of the previous problem one is such that dissolving the associated linear programming problem give the solution in which all the values are integers. So again, we do not have to explicitly introduce constraints stating that the values must be integers. We solve about linear programming problem for each specified value of alpha starting from one and increasing it by one each time. Note that when alpha equal to 1, the project completion time T equals 10. The solution to the linear programming problem gives the minimum incremental barrel cost for each specified reduction alpha in the value of the project completion time from it's normal completion time of 11. The next problem, that is problem 3, suppose the bonus for completing the project early is 50 per unit reduction in the project completion time from its normal completion time of 11 weeks. We want to maximize the net revenue, which is the bonus including the reduction in overhead costs, the unit reduction in the project completion time that is received minus the incremental data caused due to the reduction in the duration of some activities. Then the constraints remain the same as in problem two, but the objective function is changed to maximize 50 times alpha minus 25*RB-25*RC-30*RE. The objective function is to maximize the net revenue, which consists of the bonus of 50 for each unit reduction in the project completion time minus the increase in direct cost due to reducing the duration of some activities. Solving this linear programming problem gives optimal reduction in project completion time and associated activity durations. All of them being integers, which in turn imply the associated increase in direct cost. In the next problem, problem four is to address non-linearity in increase in direct costs. The linear programming problem that we have formulated, that is problem two to find out the minimal incremental cost for each specified value of the project completion time can be modified to handle a certain type of non-linearity in the relationship between activity duration and its direct cost. We will illustrate this for the example we've been considering. Suppose now that the first unit of reduction of activity we cost 25 and the second unit of reduction of activity would cause more than 25 say, 30. Now in the formulation of problem two, we replace RB by RB1+RB2 in the constraints on start times implied by the precedence relationships. In the upper bound constraints, RB less than or equal to 2 is replaced by RB1 less than or equal to 1 and RB2 less than or equal to 1. In the non-negativity constraints, RB greater than or equal to 0 is replaced by RB1 is greater than or equal to 0 and RB2 greater than or equal to 0. Finally, in that vector function, 25*RB is replaced by 25*RB1+30 times RB2. Note that before the second reduction in the duration of activity B has taken, the first reduction in the duration of activity B should have been taken. In other words, RB2=1 should imply that RB1=1. Or equivalently, the constraint RB1 greater than or equal to RB2 should be satisfied. Notice the constraint RB1 greater than or equal to RB2, together with the restriction that the variables RB1 and RB2 must be integers 0 or 1 implies that whenever RB2 equals 1, we must have RB1 equal to 1. Fortunately, the objective coefficients of RB1 and RB2 are such that it is never optimal to have RB2 equal to 1 and RB1 equal to 0, because such a solution is dominated in terms of the objective function by the solution RB1 equal to 1 and RB2 equal to 0 with the values of the other variables remaining the same. Hence, for considerations for optimal solution, we do not have to impose a restriction RB1 greater than or equal to RB2. With the above changes in the formulation of the problem, the structure of the constraint is such that an optimal solution will have an integer value for all the variables. So in this case also, we do not have to explicitly introduce constraints stating that the variables must be integers. It should be noted that for illustration, we have given the above four formulations for a small example. In practice, large linear programming problems can be solved routinely in a matter of a few seconds or minutes even if the problem is large sized say, if it's several thousands of constraints and variables. Finally in that case, suppose a second unit of reduction in the activity B cost less than the first unit of reduction in the duration of the same activity. In this case, suppose the first unit of reduction cost 25 while the second unit of reduction cost only 20. Now we must explicitly introduce the constraint RB1 greater than equal to RB2 for otherwise, may end up with a solution in which RB2=1 and RB1=0 which is meaningless. Unfortunately, when the constraint RB1 greater than equal to RB2 is explicitly introduced in the constraint set, the integrity property of an optimal solution may be lost. In other words, with the RB1 greater than or equal to RB2 in the constraint set, a linear programming solution may have fractional values for some variables. We have to solve the problem as an integer programming problem, which differs from a linear programming problem in that some or all variables are restricted to be integers. Unfortunately, the time required to solve large size integer programming problems is highly unpredictable. And that some problems are solved quickly, but some others take a very long time even with a fast in terms of execution time, computer. This completion module on using linear programming approach for reducing the project duration. [MUSIC]