INTRODUCTION
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 tradeoff between time and cost which requires an optimum solution to complete the project. Feng et al.[1] argued that the less expensive the resources used, the more duration they require to complete an activity. Hegazy[2] 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 timecost tradeoff (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: Timecost 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.[3] 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.[4] 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 ELSayegh[5] presented a nonlinear integer programming model developed to solve the timecost optimization problem by taking into account the impact of total float loss. Eshtehardian et al.[6] 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[7] proposed a model for stochastic gradientbased TCTs in PERT networks using simulation to solve TCT problems. Criticizing the existing GAbased approach for solving TCT problems, Li et al.[8] presented an integrated machine learning and GA which generates timecost curves from historical data to solve TCT problems. Pathak and Srivastava[9] also formulated a model that integrates a fuzzy logic framework with hybrid metaheuristic to solve TCT problems within an uncertainty environment. Yang[10] 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[11] proposed a new brandandbound algorithm that uses lower bound calculation for discrete TCT problem without using timeswitch constraints. The author proposed this model to improve the previous model developed by Yang and Chen,[12] who used timeswitch constraints. Ke et al.[13] studied modeling stochastic project TCTs with timedependent activity durations. BallesterosPerez et al.[14] recently studied nonlinear TCT models of activity crashing: Application to construction scheduling and project compression with fast tracking. Chua et al.[15] also proposed a model using GA to solve conventional TCT problems with resource consideration. Robinson[16] used a dynamic programming solution to solve costtime tradeoff for CPM. In providing a modification to existing models with fuzzy sets theory, Zheng and Ng[17] developed a model for stochastic timecost optimization model by incorporating fuzzy sets theory and nonreplaceable front. Elbeltagi et al.[18] used five different evolutionarybased 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[19] presented a discrete PSO method for the largescale discrete TCT problem.[20] In another study presented a hybrid simulationoptimization approach for the robust discrete TCT problem. Mixedinteger nonlinear programming optimization model was developed by Klanšek and Pšunder[21] 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[22] 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 timecost 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, ontime 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 heuristicbased approach for timecost 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 timecost optimization problem in CPMPERT network using realistic (random) durations through simulation as input. Developing a heuristicbased timecost optimization problem by considering the risk and uncertainty of activity duration will guide decisionmakers 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 heuristicbased timecost optimization problem.
In almost all cases, the previous research papers on timecost 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 (eD_{i}) can be calculated using Eqn. (1)
Where, a_{i} is the optimistic duration of activity i, m_{i} is the most likely duration of activity i, and b_{i} 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, SimDur_{i} is the simulation duration for activity i and rand_{i} 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 eD_{i}. 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).
Costslope Computational Algorithm
The costslope 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[25] 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, Cs_{i} is the cost slope of activity i, Cc_{i} is the crash cost of activity i, Nc_{i} is the normal cost of activity i, Nd_{i} is the normal duration of activity i, and Cd_{i} is the crash duration of activity i.
Computational Steps Involved in Optimizing the Heuristicbased 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, ePCom_{path–j} is the expected project completion time on path j, and tP_{Com} 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 (LCS) 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 heuristicbased TCT optimization which describes the steps involved in analyzing the TCT problem is depicted in Figure 2.
Figure 2: Flowchart of the heuristicbased timecost tradeoff 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 heuristicbased 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
Computational Steps
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 BCDE. 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 (AEnd) = 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 LCS
Activity with the LCS 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 LCS.
No change in critical, Critical path = B – C – D – E but duration = 136 days.
Activity with LCS 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 LCS. Here, two paths are critical: Path 1: B – C – D – E = 134 days and Path B – F – E = 134 days. The LCS in Path 1 is activity D but cannot be crashed anymore since its maximum crash duration is exhausted. In Path 2, the LCS 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 timecost optimization problem. Figure 7 consists of four solutions: (a) Timedirect cost relationship, (b) timeindirect cost relationship, (c) directindirect cost relationship, and (d) timetotal 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 directindirect 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: (ad) Project timecost relationship
Figure 8: Original timecost 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 timecost 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.
CONCLUSION
The goal of this study was to apply a heuristic approach to analyze a multiobjective timecost 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 heuristicbased timecost optimization problem by considering the risk and uncertainty of activity duration will guide decisionmakers in making efficient and effective decisions in TCT optimization problems.