Abstract: One of the most challenging jobs that any manager can take on is the management of a large-scale project that requires coordinating numerous activities throughout the organization. A myriad of details must be considered in planning how to coordinate all these activities, in developing a realistic schedule and then in monitoring the progress of the project. The main aim of this study is on using Linear Programming (LP) technique to build two models. The first is to find the duration of project completion (critical path or Longest route of a unit flow entering at the start node and terminating at the finish node). The second model is built because sometimes it is required to complete a project within the predetermined deadline to keep cost at lowest possible level. Failure to do so ultimately leads to increase in total cost. This would let managers to encounter a decision situation, which activities of the project will be crashed to minimize the total cost of crashing. Thus, the second model is minimizing the cost of crashing the project’s activities to meet the desired project completion time. We use a software package (Win.QSB) to deal with all the data needed to develop schedule information and then to monitor the progress of the project. Finally, we provide a combined report of the problem via analysis the results that obtained from solving these two models to give us some flexibility in planning, scheduling and controlling.

INTRODUCTION

Construction management involves the coordination of group of activities where in the manager plans, organizes, staffs, directs and controls construction projects to achieve an object, including a specification of their interrelation ships and considering the required resources in an acceptable time span. The success of CPM is that it utilizes the planner’s knowledge, experience and instincts in a logical way first to plan and then to schedule. CPM can save money through better planning.

Construction managers are continually facing a situation in which they must take a decision whether to complete the project sooner than originally specified in the contract because of the clients request and/or to optimize the cost of expediting.

The objective of Critical Path Method (CPM) is to establish a feasible and desirable relationship between the time and cost of the project by reducing the target time and taking into account the cost of expediting. Number scheduling methods were developed for planning and scheduling of construction projects using graphical methods such as line of balance and vertical production method. These techniques are neither suitable for the scheduling of linear projects nor adequate for addressing typical challenge related to time-cost trade-off.

Fortunately, two closely related operations research techniques, LP (Linear Programming) and CPM (Critical Path Method) are available to assist the project manager in carrying out these responsibilities. These techniques make heavy use of networks to help plan and display the coordination of all the activities. We use a software package (Win.QSB) to deal with all the data needed to develop schedule information and then to monitor the progress of the project (Lawrence and Pasternack, 1999; Hillier and Liberman, 2001; O’Brien and Plotnick, 2006).

The study mainly focuses on problems faced by the management when dealing with different types of problems, approaches to deal with projects. LP (Linear Programming) is used for developing two models. The first is to determine the critical activities then find a critical path (longest path in the project network). The second model is minimizing the cost of crashing the project’s activities to complete project in the desired time.

MATERIALS AND METHODS

Linear programming technique to find the critical path for the project network: We know linear programming is a tool for decision making under certain situation. So, the basic assumption of this approach is that we have to know some relevant data with certainty. We are interested in finding the critical path or the longest route of a unit flows entering at the start node and terminating at the finish node.

The following terms need to illustrate:

Thus, the objective function of linear programming becomes:

(1)

This objective function is subject to some constraints. These constraints can be classified in to three categories.

(2)

(3)

Node i: For each node, there is one constraint that represents the conservation of flow: total input flow = Total output flow.

In this formulation, the Y_i = 0 or 1 denotes the absence or presence of unite flow from node to another. So the (Eq. 4) is:

(4)

All the decision variable Y_i≥0

Linear programming technique to meet the desired project completion time: The basic data requirements are as follows:

To reduce the time to complete the activity, more resources are applied in the form of additional personnel and overtime. As more resources are applied, the duration is shortened, but the cost rises. When the maximum effort is applied so that the activity can be completed in the shortest possible time. The equation for the cost slope is

(5)

Where,

C_c and C_n=The crash and normal costs, respectively

T_c and T_n=The crash and normal times for the same activity

The cost slope shows by how much the cost of the job would change if activities were sped up or slowed down. In general, the steepness of the cost slope increases as an activity is accelerated (Senouci and Eldin, 1996; Islam Mohammad Nazmul et al., 2004; Nicholas, 2004).

Before formulating the model, let us define some relevant terms. We know, a project is the combination of some activities, which are interrelated in a logical sequence in the sense that the starting of some activities is dependent upon the completion of some other activities. These activities are jobs, which require time and resources to be completed. The relationship between the activities is specified by using event. As an event represents a point in time that implies the completion of some activities and the beginning of new ones, the beginning and end point of an activity are thus, expressed by two events.

Now let’s define the variable of the problem.

The objective is to minimize the cost of crashing total project via minimize the durations of crashing activities that multiplied by their associated costs slope, then adding the resultant cost to the normal cost of project completion. The LP objective function will be:

(6)

This objective function is subject to some constraints. These constraints can be classified in to three categories.

Crash time constraints: We can reduce the time to complete an activity by simply increasing the resources or by improving the productivity, which also requires the commitment of additional resources. But, it is not possible to reduce the required time to complete an activity after a certain threshold limit. Strive for such intention will result in superfluous resources employment which will be an inefficient approach. That is why, the allowable time to crash an activity has a limit.

Constraints unfolding the network: These set of constraints describe the structure of the network. As we mention earlier that the activities of a project are interrelated, the starting of some activities is dependent upon the completion of some other activities; we must have to establish research sequence of the activities through constraints.

Project completion constraints: This constraint will recognize that the last event (completion of last activities) must take place before the project deadline date.

Nonnegative constraints: All decision variable must ≥0. So, the constraints are:

Crash time constraints: X_q≤ Allowable crashing time for activity q measured in terms of days, weeks, months or some other units.

Constraints unfolding the network: There will be one or more constraints for each event depending on the predecessor activities of that event.

As the event 1 will start at the beginning of the project, we begin by setting the occurrence time for event 1 equals to zero. Thus, Y₁ = 0.

The other events will be expressed as follows: start time of this activity (Yi) = (start time + normal duration -crash duration) for this immediate predecessor.

Project completion constraints: Y_m≤ project deadline after being stretched, where m indicate the last event of that project (Elmaghraby and Pulat, 1997; Natarajan et al., 2005) (Fig. 1).

Hypothetical project: The construction projects Co. decided to accept the offer to construct a new plant. The maximum budgeting that available for the client is $B, but he desire to complete the plant in F time unit. It is useful at this point to illustrate the procedure with a numerical example with hypothetical data in which there are 23 activities. Table 1 summarizes a project with hypothetical data for the example.

The following terms need to illustrate.

Fig. 1:	Project network shows the critical path (bold arrows) in normal conditions critical path

Table 1:	Activity data in normal and crash conditions

Where, A_i = (A,B,C, …, W), B = $6,830,000, F = 50, T.C_N = 5,120,000, T.C_a =6,830,000.

The project manager decides to use the linear programming technique to build two models, the first is to determine the critical activities then find duration of project completion (critical path or longest path in the project network).

The management looks forward to the challenge of bringing the project in on schedule. However, since it is a doubts that it will be feasible to finish the project within F time unit in normal work conditions, the cost and time of completing the project activities under normal conditions is $Cn , Tn time unit respectively. So, the aim of second model is minimizing the cost of crashing the project’s activities to meet the desired project completion time.

Model 1. To determine the project completion in normal conditions: We can find the objective function of linear programming technique:

(7)

S. to

Nonnegative constraints: All the decision variable Y_i≥0 i.e., A, B, ... , W≥0

RESULTS AND DISCUSSION

Solution summary table (Model 1): Solution of the model is presented in Table 2, which shows the solution of the problem. It includes the decision variable value, contribution to the objective and reduced cost of each decision variable. This also indicates the status of whether the decision variable is on the final basis. This table is available when the optimal solution is achieved.

Solution summary in Table 2 specially column 3 (Solution value) or column 7 (Basis Status) indicates that an activities A, B, C, D, E, G, H, I, K, L, R, S, U, W are critical activities and others are non. Also the result indicates that activities A, B, C, D, E, G, H, I, K, L, R, S, U, W should be completed in 2, 3, 2, 2, 4, 2, 10, 4, 2, 9, 4, 6, 7, 5, 15, respectively, so the duration to complete the project in normal conditions is 77 weeks. This table contains some important columns:

The reduced cost: The reduced cost of the non-basic variables (the variables whose value is zero in the optimum solution) provide us the information about how much objective coefficients of these variables should be increased to have a positive value of those variables in the optimum solution.

In the example, reduced cost of a current non-basic variable F is -5. It means the current coefficient of this variable which is now 3 must increased 5. That means the coefficient would be 8 or up to get a basic value of this variable in the optimum solution (Table 2 Column 6) (Lawrence and Pasternack, 1999).

Sensitivity analysis for OBJ: This analysis shows the ranges of the objective function coefficients such that the current basis holds. For each decision variable, this includes the lower limit and upper limit allowed for its objective function coefficient so that the variable stays in basis, i.e., a basic variable. This is also called the range of optimality. This Analysis is available when the optimal solution is achieved.

In the hypothetical example, the final value of variable A in the objective function is 1. The current coefficient of the variable is 2, allowable Max. c(j) (Table 2 Column 9) is M (infinity) and allowable Min. c(j) (Table 2 Column 8) is -M (infinity negative). It indicates our current solution would remain optimum whatever were the increasing or decreasing in normal duration for activity A. While, the current coefficient of the variable F is 3, allowable Min. c(j) is -M (infinity negative) and allowable Max. c(j) is 8. It indicates our current solution would remain optimum if normal duration for activity F varies from -M to 8.

Constraint summary table: This table shows the constraint status of the problem for the final solution. It includes the left-hand side, right-hand side, surplus or slack and shadow price of each constraint. This also indicates the status of whether the constraint is tight or not. This command is available when the optimal solution is achieved. This table contains some important terms too:

Table 2:	Solution summary by using Win.QSB program

Table 3:	Solution of constraint summary by using Win.QSB program

Shadow price: The shadow price of a constraint is the marginal change of the objective function when the right-hand side value of that constraint increases by one unit, for example the objective function is increased 2weeks if the right-hand side value of the second Constraint (C2) increases by one unit (Table 3 Column7).

Sensitivity analysis for RHS: This Analysis shows the ranges of the right-hand sides such that the current basis holds. For each constraint, this includes the lower limit and upper limit allowed for its right-hand side so that the current basic variable is still feasible. This is also called the range of feasibility.

This analysis is available when the optimal solution is achieved.

Right hand sensitivity of the constraints provides us information regarding the status of the constraints- which of these constraints are binding (fully utilized) or non-binding.

Binding constraints having a value in the shadow price column (Table 3 Column7) other than zero, means how much contribution these binding constraints will provide individually in the objective function, if the value of the right hand side of these constraints are increased by 1 unit.

The allowable min. RHS and allowable max. RHS columns in Table 3 indicate the range of allowable decrease and range of allowable increase of the right hand side value of the binding resources within which the current shadow price would remain unchanged. So, this model would help management to reach the optimality where sensitivity analysis would provide some flexibility in the model. So the right hand side of the C1 is -1, allowable min. c(j) is -M and allowable max. c(j) is -1. It indicates our current solution would remain optimum if C1 varies from -M to -1.

Table 4:	Head and tail events activities

Model 2. To crash the duration of project completion: For the purpose of modeling the problem, it is necessary to define the activities in terms of starting and ending event. The total number of events in this project is 18 (Table 4).

Objective function of (Model II):

(27)

This objective function subject to the following constraints:

Maximum reduction constraints:

Start time constraints: We begin by setting the event occurrence time for event 1 to be Y₁ = 0. The constraints describe the structure of the network are as follows:

Or,

Or,

Or,

Or,

Or,

Or,

Or,

Nonnegative constraints: All the decision variable Y_i≥0 i.e., A, B, C, .., W≥0.

As the manager wants to complete the project within 50weeks, so the last event should be completed before or on 50th week. By analyzing the project on crash time basis the expected date of completion of the project is 50 weeks. So, the maximum extent of crashing the project is 46 weeks. Beyond this time period, the project cannot be crashed.

Solution summary table (model 2): Solution summary for model 2 is presented in Table 5, which shows the solution of the problem.

Solution summary in Table 4 indicates that an activity A should be crashed at 1 weeks, B at 2 weeks, C at 1week, etc. (Table 5). Subtracting the crash-time amounts from the normal completion, the result indicates that activity A should be completed in 1 week, B in 1 week, C in 1 week, etc. the adding cost(crash cost) by crashing critical activities to reduce the project duration within 50 weeks is $970,000 and the cost to complete the project in normal duration(77 weeks) is $5,120,000. So, the final project cost is computed by adding cost (crash cost) by crashing critical activities $970,000 to the normal cost $5,120,000. So, the final project cost is $6,090,000.

Table 5:	Solution summary by using Win.QSB program

The reduced cost of the non-basic variables (the variables whose value is zero in the optimum solution) provide us the information about how much objective coefficients of these variables should be increased to have a positive value of those variables in the optimum solution.

In the example, reduced cost of a current non-basic variable X_F is 30,000.

It means the current coefficient of this variable which is now 30,000 must increased 30,000 (that means the coefficient would be 60,000 or up) to get a basic (positive) value of this variable in the optimum solution (Table 5).

Sensitivity analysis for OBJ shows the ranges of the objective function coefficients such that the current basis holds. In our hypothetical example, the final value of variable X_A in the objective function is 1. The current coefficient of the variable is 10,000, allowable min. c(j) is -M and allowable max. c(j) is 75,000 (Table 5). It indicates our current solution would remain optimum if crash cost per unit of time for activity A varies from -M to 75,000.

Constraint summary table: Constraint summary indicates the status of whether, the constraint is tight or not. This command is available when the optimal solution is achieved.

The slack variable is the variable added to the left-hand side of a less than or equal to constraint to convert the constraint into an equality. The slack variable is the starting basic variable for the constraint. It can be interpreted as the unused resource or right-hand side.

Table 6:	Solution of constraint summary by using Win.QSB program

The surplus variable is the variable subtracted from the left-hand side of a greater than or equal to constraint to convert the constraint into an equality. It can be interpreted as the amount over the requirement or right-hand side. So, we can notice the slack for binding constraints (fully utilized) are zero (Table 6 Column 6).

The shadow price of a constraint is the marginal change of the objective function when the right-hand side value of that constraint increases by one unit. So, the objective function is increased $65,000 if the right-hand side value of the first Constraint (C1) increases by one unit (Table 6 Column 7).

Right hand sensitivity of the constraints provides us information regarding the status of the constraints-which of these constraints are binding (fully utilized) or non-binding.

Binding constraints having a value in the shadow price column (Table 6) other than zero.

The allowable min. RHS and allowable max. RHS columns in Table 6 indicate the range of allowable decrease and range of allowable increase of the right hand side value of the binding resources within which the current shadow price would remain unchanged. So, this model would help management to reach the optimality where, sensitivity analysis would provide some flexibility in the model, for example the right hand side of (C1) is 1, allowable Max. c(j) is 0 and allowable Max. c(j) is 2. It indicates our current solution would remain optimum if constraint1varies from 0-2.

CONCLUSION

These models will provide us systematic and logical approaches for decision making and ultimately increases the effectiveness of the decision. As the solution of these models by software package (Win.QSB) provide us the duration of project completion in normal and crash conditions, also gives us some flexibility by providing a combined report of the problem, which includes the solution value, contribution to the objective, reduced cost and range of optimality for each decision variable and right-hand side, surplus or slack, shadow price and range of feasibility for each constraint.

In this reseaech, we also propose an algorithmic model based on linear programming incorporated with a minimal time-cost trade-off in a construction project. The format of the model lends itself to a wide range of variables and considerations.

The present modeling strategy has shown the resources of this interactive approach including a bulk of data to completely analyze the project is easily possible. It allows a great number of parameters to simulate project conditions and contractor's preference and provides potentially useful tool for decision making on project scheduling.

The cost of the network activities has been optimized for various overall duration. The optimum trade-off of time against cost has been made. This approach is an acceptable tool of management and proving to be not only superior method for planning, scheduling and controlling project progress, but also is very real and valuable assets to contractors in convincing the owner of their potentials and abilities. With the introduction of better and more rigorous methods of planning research, together with cost analysis, the construction control will become more systematic. Mathematical models are used more and more for executive planning functions. In all of these, decisions must be made to carry out the operation in the best way possible in light of the restraints that are bound to exist.

This approach allows the user to easily manipulate different project networks of various difficulties representing real world applications and to study the effectiveness of the model in the case of large projects. The implementation of the developed model is tested on a large number of linear optimization problems and shown to have more efficient and reliable results, generates a considerable computational savings, along with an increase in robustness.

Defining the variables:

Let,