Completing projects at a minimal time and within a minimum cost are the main objectives of construction projects. The need for work from contractors has resulted in clients tightening their requirements. Project managers are under intense pressure to complete the project under tight deadlines subject to huge penalties if they failed to complete the project within the stipulated deadline. One of the best solutions to meeting deadline projects has been the use of crashing technique to shorten the project duration. However, as the project’s duration is reduced, the total project cost increases and the more the project’s duration is shortened, the more the total cost increases. This means that there is a trade-off between time and cost which requires an optimum solution to complete the project. Feng et al. argued that the less expensive the resources used, the more duration they require to complete an activity. Hegazy supports this argument with an example that using more productive equipment or hiring more workers may save time but may result in increased cost. Figure 1 depicts the relationship of time-cost trade-off (TCT), showing the normal and crash duration and the corresponding normal cost and crash cost for completing an activity using different construction options as P1, P2, P3, and P4. In any case, resource allocation decisions made during the early start of the activities control the overall project time and cost of the project. Finding the most desirable duration and cost to complete a project is the major challenge of project planners. However, since a project should be executed to yield a profit for the organization, project planners must utilize effective means to complete the project within a limited time. The critical path method (CPM) has been the project planners’ favorite project planning technique. The CPM helps to identify the critical activities which may impact the overall project’s completion duration if delayed. This presents project planners the opportunity to identify those critical activities and use the appropriate resources to complete each activity. Hence, to perform TCT analysis, activities on the critical path can be crashed to reduce their duration and using optimum resources to minimize the total project cost. Several studies have been conducted on TCT problems to discuss the feasible techniques to solve TCT problems in construction projects.
Figure 1: Time-cost relationship of an activity
TCT concept has been defined and explained in many ways by different authors. The TCT is defined by Abbasnia et al. as a process to identify suitable construction activities for speeding up and for deciding how much so as to attain the best possible savings in both time and cost. The TCT can also be defined as the process of finding the optimum time at which the project can be completed within a desirable minimum cost. In their research, Azaron et al. applied genetic algorithm (GA) technique to develop a multiobjective model for TCT problem in program evaluation and review technique (PERT) network with generalized distribution of activity durations. Al Haj and EL-Sayegh presented a nonlinear integer programming model developed to solve the time-cost optimization problem by taking into account the impact of total float loss. Eshtehardian et al. also investigated stochastic TCT problems using GA and fuzzy logic theory that accounts for uncertainties in cost to help select specific risk levels. In an attempt to characterize the amount of variability in networks, Bowman proposed a model for stochastic gradient-based TCTs in PERT networks using simulation to solve TCT problems. Criticizing the existing GA-based approach for solving TCT problems, Li et al. presented an integrated machine learning and GA which generates time-cost curves from historical data to solve TCT problems. Pathak and Srivastava also formulated a model that integrates a fuzzy logic framework with hybrid metaheuristic to solve TCT problems within an uncertainty environment. Yang analyzed the impact of budget uncertainty on project TCT and found that a higher degree of budget uncertainty presents a tighter financial constraint, which needs an extra contingency. Vanhoucke proposed a new brand-and-bound algorithm that uses lower bound calculation for discrete TCT problem without using time-switch constraints. The author proposed this model to improve the previous model developed by Yang and Chen, who used time-switch constraints. Ke et al. studied modeling stochastic project TCTs with time-dependent activity durations. Ballesteros-Perez et al. recently studied nonlinear TCT models of activity crashing: Application to construction scheduling and project compression with fast tracking. Chua et al. also proposed a model using GA to solve conventional TCT problems with resource consideration. Robinson used a dynamic programming solution to solve cost-time trade-off for CPM. In providing a modification to existing models with fuzzy sets theory, Zheng and Ng developed a model for stochastic time-cost optimization model by incorporating fuzzy sets theory and non-replaceable front. Elbeltagi et al. used five different evolutionary-based optimization models (GA, memetic algorithm, particle swarm optimization [PSO], ant colony, and shuffled frog leaping) to solve TCT problem and compared their results. Aminbakhsh and Sonmez presented a discrete PSO method for the large-scale discrete TCT problem. In another study presented a hybrid simulation-optimization approach for the robust discrete TCT problem. Mixed-integer nonlinear programming optimization model was developed by Klanšek and Pšunder to solve nonlinear discrete TCT problems.
The heuristic method has been and still remains one of the most useful techniques to solve TCT problems. Siemens was among the first to have used the heuristic method, through cost ratio approach to solve TCT problems. Recently, some researchers have also used the heuristic algorithm to model time-cost optimization in a construction project. Biswas et al. and Nikoomaram et al.[23,24] adopted a heuristic method to develop a model to solve different TCT problems in construction projects.
Despite the useful application of the heuristic method to solve TCT problems, these models mainly use deterministic durations to model the TCT problem. However, in reality, activities may not be completed as planned. Some activities may take a longer time to complete, while others may take a shorter time to complete. The uncertainties in the activity duration may affect the project duration, as well as the cost. Using deterministic activity durations may lead to the wrong selection of construction options (resource allocation), thus leading to selecting the wrong optimum solution to TCT problem. Uncertainty variables may include productivity rate, on-time availability of resources on site before starting an activity, and weather conditions. Hence, to improve the accuracy of optimum solution in TCT analysis, this study presents a heuristic-based approach for time-cost optimization by taking into account the impact of risk and uncertainty of activity duration. This was done by using a probabilistic approach through simulation to develop realistic durations and use these durations as input to reschedule the critical path method (CPM) network. Simulation deals with the uncertainties of activity duration in a project.
This study developed a multiobjective time-cost optimization problem in CPM-PERT network using realistic (random) durations through simulation as input. Developing a heuristic-based time-cost optimization problem by considering the risk and uncertainty of activity duration will guide decision-makers in making efficient and effective decisions in TCT optimization problems.
MATERIALS AND METHODS
In this section, we will formulate the heuristic model that accounts for risk and uncertainty in the activity durations by generating simulation durations and reschedule the CPM network. The next subsections will explain how the simulation durations are calculated and computational steps involved in solving a heuristic-based time-cost optimization problem.
In almost all cases, the previous research papers on time-cost optimization through crashing of activity duration have been applied on construction projects. Therefore, this paper will also focus on applying the model on a simple construction project.
Generating Random Duration
To account for the uncertainty of activity duration, Monte Carlo simulation is applied. Activity duration can be simulated using probability distributions. In this study, we used triangular distribution to model random durations. In the triangular distribution technique, the expected duration of activity i (eDi) can be calculated using Eqn. (1)
Where, ai is the optimistic duration of activity i, mi is the most likely duration of activity i, and bi is the pessimistic duration of activity i. However, we used the probability distribution of triangular distribution to generate random or simulated duration for each activity. In each activity, a triangular distribution was assigned and the random duration was generated. We show how simulation durations using the triangular distribution were modeled in Microsoft Excel. We first established the optimistic, most likely and pessimistic durations for each activity. Then, we created a custom variable called Cvar using Eqn. (2), after which random number between 0 and 1 were generated. Finally, random activity durations were generated using Eqn. (3).
Where, SimDuri is the simulation duration for activity i and randi is a random number generated for activity i.
These generated random durations are further simulated many times, and in this study, we used 10,000 iterations to find realistically eDi. Visual basic for application (VBA) was used to perform this iteration, and these generated durations become the actually expected durations to be used to prepare the network diagram (with activity uncertainty taken care of).
Cost-slope Computational Algorithm
The cost-slope method is the main heuristic method for TCT analysis deployed to reduce the project duration based on the fundamental assumption that the relationship between time and cost is linear. With this common assumption, cost slope of activity i is defined by Hegazy as the rate at which the direct cost increases when the duration of that activity is reduced by a unit of time. To calculate the cost slope of each activity in the network, Eqn. (4) was used.
Where, Csi is the cost slope of activity i, Cci is the crash cost of activity i, Nci is the normal cost of activity i, Ndi is the normal duration of activity i, and Cdi is the crash duration of activity i.
Computational Steps Involved in Optimizing the Heuristic-based TCT Problem
The objective here is to minimize the total cost of shortening the project duration to meet specific deadline such that the project’s profit is not much affected:
Use the simulation durations for all activities
Develop the CPM network
Calculate and identify all the paths in the network (path with the longest expected duration = critical path)
Determine the amount required to reduce each path in the CPM network. The amount to be reduced on each path can be computed using Eqn.
Where, Λpath–j is the amount to be reduced on path j, ePCompath–j is the expected project completion time on path j, and tPCom is the targeted project completion time.
Calculate and tabulate the cost slope for each activity as well as defining the maximum crashing amount
Crash the critical activity with the least cost slope (LC-S) first based on the maximum amount to be crashed. If two or more critical paths occur, crash the activity appearing in both paths, or crash both activities with the minimum cost slope in each path.
Reschedule the CPM network using the crashed duration for that activity and calculate the project duration if the critical path does not change, continue to crash the activity until its maximum crash duration is exhausted.
Determine the total direct cost by multiplying the cost slope of the activity by the amount reduced, as well as the corresponding indirect cost by multiplying the estimated cost per day by the expected project duration.
Continue from step (g) until the deadline duration is reached.
Plot the total increase in direct cost against the resultant crash duration. Plot also the total project cost (direct + indirect costs) on the same graph and determine the optimum option with the least total cost.
The flowchart of the heuristic-based TCT optimization which describes the steps involved in analyzing the TCT problem is depicted in Figure 2.
Figure 2: Flowchart of the heuristic-based time-cost trade-off optimization
NUMERICAL EXAMPLE PROBLEM AND ANALYSIS
An example problem from a small construction project is considered to demonstrate the applicability and the impact of duration uncertainties on heuristic-based multiobjective TCT analysis. The scheduling project considered was previously applied to solve TCT problem by Biswas et al., 2016, using the heuristic method. For example, problem consists of six activities. The indirect cost of the project is assumed as $100/day. The project data with deterministic durations are shown in Table 1, which consist of activity names and their corresponding durations. Using the deterministic durations, the project was scheduled to be completed in 140 days.
Table 1: Project data with deterministic durations
With reference to the data of the example problem, realistic durations through simulation were developed as shown in Table 2. These random durations are to be used as the expected duration of each activity. To avoid decimals in the activity durations, any duration above 0.5 days was taken as 1 day. Table 3 shows the realistic durations of the activities, as well as the crash duration, normal cost, and the crash cost. Deploying the forward and backward technique, the early start time, early finish time, late start time, and late finish time durations were calculated to determine the total project completion time. The expected project completion time from the network diagram is 144 days and the critical path is B-C-D-E. The total direct cost of all the activities amounts to $49,805.
Table 2: Realistic duration of activities generated through simulation
Table 3: Detailed project information of the example problem
To expedite the project, an optimization approach was used to reduced the project completion time of 144 days. In normal project crashing, reducing the duration increases the direct cost but decreases the indirect cost. Therefore, if the indirect cost is less than the direct cost, then an optimal or minimal cost can be achieved. Hence, the project can be crashed until the activity indirect cost becomes greater than its direct cost resulted from crashing the duration. However, in this study, a target completion time of 124 days was used to find the optimal cost of reducing the project duration of 144 days.
The network diagram in Figure 3 consists of three paths: Path 1 (B – C – D – E) = 144 days; Path 2 (B – F – E) = 134 days, and Path 3 (A-End) = 118 days. Determining their amount to be crashed, Path 1 can be crashed by a total of 20 days (144–124) while Path 2 can be crashed by a total of 10 days (134–124). Path 3 needs not to be crashed since its completion time is less than the targeted completion time. In Table 4, the calculation of the cost slope of all the activities is presented. It is important to compute the cost- slope of all the activities and not just the critical path activities, in that the path can change after crashing an activity and will need such information.
Figure 3: Activities precedence network diagram
Table 4: Cost slope of activities in the network
Using these realistic expected durations from simulation, the CPM network is drawn as depicted in Figure 3. With the cost slope of each activity computed, the detailed analysis of the cycle computation of the total direct cost and indirect cost resulting from crashing the critical activities duration can be summarized as follows:
1st cycle: This cycle uses the initial CPM data, where the total project completion duration = 144 days. Indirect cost = 144 days *100/day = 14400 and total direct cost = 49805. Total project cost = (49805+14400) = 64205
2nd cycle: Identify critical path and activity with LC-S
Activity with the LC-S of this critical path = activity D (60) and this activity can be crashed by at least 8 days. Therefore, activity D becomes 22 days and the CPM is recalculated as shown in Figure 4. There will not be any change in the critical path. The total project completion duration = 136 days. Indirect cost = 136 days *100/day = 13600 and total direct cost = 49805 + (8*60) = 50285. Total project cost = (50285 + 13600) = 63885.
Figure 4: Precedence network diagram after crashing activity D
3rd cycle: Identify critical path and activity with LC-S.
No change in critical, Critical path = B – C – D – E but duration = 136 days.
Activity with LC-S of this critical path is still = activity D (60) which can further be crashed by 2 days. Therefore, activity D reaches its maximum crash duration of 20 days and the CPM is recalculated as shown in Figure 5. The total project completion duration = 134 days. Indirect cost = 134 days *100/day = 13400 and total direct cost = 49805 + [(2*60) + (8*60)] = 50405. Total project cost = (50405 + 13400) = 63805
Figure 5: Precedence network diagram after crashing activity D second time
4th Cycle: Identify critical path and activity with LC-S. Here, two paths are critical: Path 1: B – C – D – E = 134 days and Path B – F – E = 134 days. The LC-S in Path 1 is activity D but cannot be crashed anymore since its maximum crash duration is exhausted. In Path 2, the LC-S is activity E which is also the least considering Path 1 when D is out. In this situation, both B and E can be crashed. Activity B and E both can crash by at least by 5 days. Hence, activity B becomes 17 days and activity E becomes 45 days (359; sum of 239 cost slope of B and 120 cost slope of E) and the network is recalculated as depicted in Figure 6. The total project completion duration = 130 days. Indirect cost = 124 days *100/day = 12400 and total direct cost = 49805 + (5*359) = 51600. Total project cost = (50330 + 12400) = 64000
Figure 6: Precedence network diagram after crashing activity B and E
In Table 5, the summary of the analysis results is presented. The first column shows the project duration, while the next columns show the corresponding indirect, direct, and the total costs resulting from optimizing the project duration by shorting the original project duration of 144 days in an attempt of expediting the project.
Table 5: Summary of associated costs of crashing the project duration
Figure 7 presents detailed results of the time-cost optimization problem. Figure 7 consists of four solutions: (a) Time-direct cost relationship, (b) time-indirect cost relationship, (c) direct-indirect cost relationship, and (d) time-total cost relationship. It can be seen in Figure 7a that as project duration is crashed to a minimum duration, the direct cost of the project increases. On the other hand, in Figure 7b, reducing the total project duration decreases the indirect cost linearly. The direct-indirect cost relationship in Figure 7c shows that as direct cost increases as a result of shortening the project duration, indirect cost decreases. The optimal solution, for example, problem is depicted in Figure 7d, where the optimum solution occurred at 134 days and at a minimum total project cost of $63,805. In Figure 8, the comparison of the original project schedule of time and cost against the total project’s time and cost after crashing the project for the expedition is presented.
Figure 7: (a-d) Project time-cost relationship
Figure 8: Original time-cost plan against optimization time cost
DISCUSSION AND RESULTS
This section discusses the results from the analysis of the TCT problem. Time and cost, which are independent of each other, are the two important attributes of any project. It is the objective of the project management team to complete the project within a minimum time and at the same time within a minimum cost. However, it is not easy to satisfy these two conflicting objectives at the same time. Optimization has been identified as the most suitable technique to model this kind of the problem of conflicting factors where an attempt to optimize (reduce) one objective increases the other objective factor. The results in Figure 7a show that as the project original duration is shortened through crashing, i.e., from 144 days to 124 days, the total direct cost increased from $49,805 to $51,600. The results in Figure 7b and Figure 8 show a decrease in the total project cost from $64,205 to $63,325 as project duration reduces. However, at some point, the total project cost increases again as the project is further reduced. After 134 days, where the total cost occurred at a minimum of $63,325, the total cost increased again to $64,000 at a duration of 124 days. This explains the real behavior of projects and the concept of optimization in construction projects. The time-cost optimization, for example, problem results in a minimum total project cost of $63,325 and with a total project duration of 134 days. The minimum total cost is achieved because every time the project duration is reduced, the total indirect cost is decreased. This suggests that the project can be done in 134 days instead of the original 144 days, and within a minimum cost of $63,325, saving about $880 from the original CPM schedule of $64,205. The results of this study are accurate and reliable and are better than the results presented by Biswas et al., 2016, who used deterministic activity durations in the TCT problem and found the optimum solution at 130 days. However, because this study incorporated risk and uncertainty analysis using probabilistic approach through simulation to generate realistic (random) activity durations, an accurate optimum solution was achieved at 134 days and a minimum total cost of $63,325. An accurate and reliable optimum solution from the TCT analysis will help the project management team to make better decisions on effectively allocating resources to complete the project.
The goal of this study was to apply a heuristic approach to analyze a multiobjective time-cost optimization problem by considering the impact of risk and uncertainty of activity durations on achieving the optimum solution of the TCT problem under consideration. The study used a probabilistic approach through simulation to develop realistic durations and use these durations as input to reschedule the CPM network. A heuristic technique was used to crash the activity durations and the total project duration. A total of 10 days was reduced from the original CPM schedule of 144 days which has considered uncertainties in the activity durations. This reduction increased the total direct cost of the project from $49,805 to $50,405. This indicates that about 13.9% decrease in total project duration is achieved by increasing the total cost of the project by just 1.2%, which is quite satisfactory. Developing a heuristic-based time-cost optimization problem by considering the risk and uncertainty of activity duration will guide decision-makers in making efficient and effective decisions in TCT optimization problems.