 Open Access
 Authors : Yusuf Baltaci , Mohammad Azim Eirgash
 Paper ID : IJERTV10IS040152
 Volume & Issue : Volume 10, Issue 04 (April 2021)
 Published (First Online): 24042021
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Application of Siemenss Effective Cost Slope Approach on TimeCost TradeOff Optimization Problems
Yusuf Baltaci, Mohammad Azim Eirgash Ph.D. Candidate Karadeniz Technical University Department of Civil Engineering
Turkey Trabzon. 61000
Abstract: – Timecost tradeoff (TCT) analysis is accepted as a significant aspect of any construction project planning. Both the client and contractor would be willing to contribute for the fasttracking as well as crashing of construction project. Optimization of time and cost results in simultaneous minimization of total project duration and total project cost. Accelerating the project schedule will rise the cost and shall be productive only up to a certain limit. Thus, the construction manager has to consider the time cost tradeoff and identify the alternatives that optimizes both time and cost to enhance the overall construction project benefit. In this paper, Siemenss effective cost slope optimization model, which minimizes the total project time and cost, is carried out on timecost tradeoff. Two important objectives in project planning: (1) minimizing total project duration, (2) total project cost are taken into account in the simultaneous optimization of TCT problem. The concept of the SAM (Siemenss Approximation Moldel) is explained through a time cost problem to evaluate the performance of the applied method. The obtained result indicates that the model could assist decisionmakers in concurrently arriving at an optimal project duration and total cost as well. .
Keywords Time Cost Tradeoff; FastTracking; Crashing; Siemenss cost slope algorithm.
I. INTRODUCTION
In todays hurry up construction field, the force and pressure is on to complete the project within the given deadline. And both client and contractor are enthusiastic about paying for on – time project completion. This favorable target is achieved by finding the optimal set of timecost alternatives and is known as timecost tradeoff problem in the literature. Moreover, timecost tradeoff the analysis is a critical part of any construction works and both the researchers as well as contractors are interested in paying attention to this subject, because of the academic/real field nature of the issue. Project managing looks for the best economical scheduling subjected to different parameters such as time, cost and other operation resources. Project scheduling calculations are based on CPM (Critical Path Method). Each activity has a normal duration and a forced duration. Completing an activity in its forced duration needs more direct cost and resources. On the other hand it leads to decrease projects total duration and indirect costs.
One method is to compress some of the activities on the Critical path is to save time cost (Siemens, 1971).Traditionally, timecost tradeoff problem (TCTP) has been addressed by mathematical programming models such as linear programming (Kelley 1961), dynamic programming (Elmaghraby 1993) and linear programming and integer programming (LP/IP) hybrid (Liu et al. 1995). However, the linear programming model requires specific assumptions for functions involved (Yang 2007) and the dynamic programming model requires numerous trials (Xiong and Kuang 2008).
Eirgash (2018) applied GA and TLBO algorithms incorporated with MAWA and NDS methods in his study. The models were tested on projects with 7, 18, 63 and 630 activities. According to the results, it was found that NDS had better results than MAWA, especially, when the number of project activities increased. Moreover, it was obtained that the model working with partial random population based on NDSTLBO had better results than the models that worked with the TLBO models previously developed.
Eirgash and Dede (2018) used the TLBO algorithm, which was developed with the assignment of different teachers to different student groups and with the adaptive teaching factor. In this study, the applied algorithm is associated with MAWA. The model, which was examined with 18 and 63 activity projects, was found to offer successful Pareto front solutions. The study achieved better results compared to similar studies in the literature.
Fig. 1 illustrates the basic relationships between indirect, direct and total project cost due to crashing.
The paper is organized as follows: In the next section we briefly define the deterministic timecost tradeoff problem, then relevant researches belong to it and performance is carried out manually with an empirical example as well as the CPM of the related example is found using Oracle Primavera P6.
Cost
Total Cost
Indirect (overhead) Costs
Therefore each activitys duration can be between two extremes: Normal duration and forced duration. Completing a project with minimal time as well as minimal cost is a
Crash Time Normal Time
Minimum Cost Solution
Direct Costs
Project Duration
critical factor for scheduling a project..
FIG.1 TIMECOST RELATIONSHIP IN PROJECTS

Timecost Trade off Problem (TCTP)
To start scheduling the project, an arbitrary date should be set for the start event in the projects network diagram. Usually this value is set to zero. Scheduling computation consists of two tracking through the network, forward tracking and backward tracking. The earliest possible date to start each activity is determined by forward tacking, and the latest possible date to finish the ones is obtained by backward tracking. The Earliest possible date to start an activity (ES) is the earliest date that all of its predecessor activities have been finished. The Latest possible date to Finish an activity (LF) is the latest date that none of its successor activities would be started. If an activity finishes after this date, it will have effect on the start dates of its successor activities.

Project Crashing
Project crashing problem is primarily concerned with the tradeoff between compressed activity duration and consequent increase in the direct cost due to crashing. In many situations, it is possible to reduce the length of a project by injecting additional resources. The crash time represents the fully expedited or the minimum activity duration time that is possible and any attempts to further crash would only raise the activity direct costs without reducing the time. The slope of crashing an activity means the increment cost of expediting the activity per unit period calculated as:
C= (Cf Cn) (Dn Df) (1)
In this formula C is the cost slope, Cf is the forced cost, Cn is the normal cost, Df is the forced duration and Dn is the normal duration of an activity.
Project crashing is a method for shortening the project duration by reducing the time of one (or more) of the critical project activities to less than its normal activity time. This reduction in the normal activity time is referred to as crashing.

Cost Slope
The additional direct cost that one has to pay to reduce one unit of time from the normal duration of an activity is defined as the cost slope. As there is not any explicit formulation for the time cost curve but some approximated forms, the linear approximation is conventionally used as a simple practical model.

SIEMENSS HEURISTIC ALGORITHM FOR TCTP PROBLEMS
In this section one of the conventional algorithms to time cost tradeoff is introduced. This common algorithm has been presented by Nicolai Siemens. The main application of Siemens algorithm concerns the projects for which a pre defined completion time (Tp) has been agreed in the contract. This deadlineis before the normal completion date calculated by CPM method. Siemens algorithm finds the best arrangement of activities in which the project will be ended up until Tp while minimizing the overhead cost.
TAi =Dn Df (2)
TAi is reducible time of activity i, D'n is the current duration of activity and Df is the forced duration of the activity. Initially D'n = Dn.
ECi =Ci / Ni (3)
ECi is the effective cost slope for activity i, Ci is the cost slope and Ni is the number of the paths passing on activity and are not "shortened enough". The path is "shortened enough" when the project can be completed at Tp so there is no need to reduce the time more.
TR=Dp Tp (4)
The necessary time reduction, TR, is equal to the current length of the path, DP minus Tp.

Siemens algorithm
Siemens algorithm is defined as follows:

Estimate activities duration on the network and perform CPM calculations based on the normal duration of activities.

For each path, compute the necessary time reduction, TR and determine which one is not shortened enough (TR > 0).

For each activity occurred on at least one of the paths determined by step 2, compute the cost slope, C, and the reducible time, TAi.

Compute the effective cost slope for the activities of step 3.

Among paths with maximum necessary time reduction, select the one of which the effective cost slope is the least. If there are more than one activity admitting such a condition, then decide upon the following criteria, respectively,

Choose the activity which occurs on more number of not shortened enough paths.

Choose the activity with the largest necessary reduction time.

Randomly choose one of the activities.


Reduce the time of the activity obtained in step 5 to the least possible value which is the minimum of the following values:

The reducible time of the activity, TAi.

The minimum necessary time reduction of the not shortened enough paths passing the activity.


Increase the duration of the activities which are reduced more than necessary time until no new not shortened enough paths would be generated. These activities occur on the paths in which Dn Tp < 0. If all paths have been shortened enough then stop, otherwise update the effective cost slopes of the activities occurring on the paths that are not short enough, then go to step 5.


Fitness Function
Depending on the purpose of resolving the problem, different fitness functions could be applied. For example if the purpose is to reduce the duration of the project from T1 to T2, duration of the project can be used as fitness value. If the objective is to reduce the cost of the project, the sum of direct and indirect costs of the project could be considered as the fitness value. But in the case that the objective is to reach the optimum point of the project, the point that both the sum of direct and indirect costs and the project time get the joint minimum, a mixed form should be used as fitness value, as follows:
Fitness(c) = Total Duration + (Direct CostIndirect Cost) (5)
Where Total Duration is the reduced duration of the project in regard to normal duration, and Indirect Cost and direct Cost are respectively the reduction in indirect cost and the addition of direct cost.

Critical Path

Those activities with the least slack will form a path through the CPM diagram from beginning to end. A sequence of project network activities which add up to the longest overall duration is known as critical path. Any delay of an activity on the critical path directly impacts the planned project completion date. CPM representation of present project is shown in Fig. 2.
FIG. 2 CPM OBTAINED USING ORACLE PRIMAVERA P6
As we observe that, the bars with red colors are critical activities i.e. AFGH which requires maximum resources like time duration, money…etc and the bars with green colors are remaining works which are not critical.
3 Numerical Problem:
The normal cost, normal duration, crash duration and crash cost of a project are given below in Table 1. If the indirect cost of the project is Rs 5000/day then the optimum total cost and minimum duration of the project is found out. The Network of the project is depicted in Fig. 3.
FIG. 3 PROJECT NETWORK
TABLE 1 THE OPTIMUM (6TH)
CRASHING
Act. 
Pred. Activity 
Normal Dn Cn 
Crash Df Cf 
Critical Act. 
TAi (Days) 
C (TL) 
A 
— 
10 12000 
6 20000 
A 
4 
2000 
B 
A 
9 12000 
7 16000 
2 
2000 

C 
B 
6 9000 
4 12000 
2 
1500 

D 
A 
4 8000 
2 13000 
2 
2500 

E 
D 
11 10000 
7 17600 
4 
1900 

F 
A 
9 9000 
6 15600 
F 
3 
2200 
G 
F 
14 15000 
10 18200 
G 
4 
800 
H 
E,G,C 
5 7000 
3 9600 
H 
2 
1300 
Indirect Cost = Rs 5000 /day
Direct Cost = Rs 82000 (Sum of total normal cost of the project).
Total Cost = Direct Cost + Indirect Cost = 82000 + 38*5000= 272000 TL.
The calculations have been carried out for the case when the project completion time is required as the optimum. Project duration depends upon the duration of critical activities, so if it is intended to reduce the project duration, then individual time duration value for each critical activity must be reduced.
Crash – 1

To reduce the project duration, it is necessary to reduce the time duration of individual critical activities. Initially , slope value for each critical activity is found and reduce ( Crash ) that activity first , which has the minimum slope value , so the activity which has the minimum slope value is activity G with 2 days reduction is possible ( Normal duration – Crash duration ) with increased cost of 800 / day. So activity G is reduced from 14 days to 12 days also project duration will reduce to 382 =36 days and total cost becomes = Direct Cost + Crashing Cost + Indirect Cost for 36 days = 82000 + 800*2+36*5000=263600 TL.
Next it is checked that, due to the crashing, any new activity has become critical or not i.e. any new critical path has formed or not. If any new critical path has formed, it is necessary to reduce the total duration of each critical path simultaneously. So in this case, till now, no new critical path has formed.
Crash – 2

Again activity G can be reduced from 12 days to 10 days, and project duration will reduce to 362 = 34 days and also total cost becomes = Dc + Cc + IDc for 34 days = 253600 TL.
Crash – 3

Now activity G is at its crash duration, no further reduction is possible, so activity which will be crashed with next minimum slope value is activity H, and 2 days reduction is possible with increased of Rs 1300 /day. If activity H is reduced from 5 days to 3 days, project duration will reduce to 34 2= 32 days. So total cost becomes = Dc
+ Cc + IDc for 32 days = 244600 TL. Crash – 4

Now activity H is at its crash duratio, no further reduction is possible, so activity which will be crashed with
300000
Total cost (TL)
Total cost (TL)
250000
200000
150000
100000
50000
0
Time cost tradeoff curve
FIG. 4 TOTAL COST VS. TOTAL DURATION OF THE PROJECT
FIG. 4 TOTAL COST VS. TOTAL DURATION OF THE PROJECT
Direct Cost (TL) Indirect Cost (TL)
38 36 34 32 30 28
Project duration (day)
next minimum slope value is activity A, and 4 days reduction is possible with increased of Rs 2000 /day. If activity A is reduced from 10 days to 8 days, project duration will reduce to 32 2= 30 days. So total cost becomes = Dc + Cc + IDc for 30 days =236000 TL
Crash – 5

Again activity A can be reduced from 12 days to 10 days, and project duration will reduce to 302 = 28 days and also total cost becomes = Dc + Cc + IDc for 28 = 226000 TL
Crash – 6

Now activity A is at its crash duration, no further reduction is possible, so activity which will be crashed with next minimum slope value is activity F, and 3 days reduction is possible with increased of Rs 2200 /day. If activity A is reduced from 9 days to 6 days, project duration will reduce to 28 3= 25 days. So total cost becomes = Dc
+ Cc + IDc for 25 days = 213600 TL. Table 2 indicates the indirect, direct and total project cost due to optimum crashing. And Fig. 4 represents the total project cost vs total duration of the project at its optimum values.
TABLE 2. THE OPTIMUM (6TH) CRASHING
Cycle 
Duration (Days) 
Direct Cost (TL) 
Indirect Cost (TL) 
Total Cost (TL) 
0 
38 
82000 
38*5000 = 190000 
272000 
1 
36 
83600 
180000 
263600 
2 
34 
83600 
170000 
253600 
3 
32 
84600 
160000 
244600 
4 
30 
86000 
150000 
236000 
5 
28 
86000 
140000 
226000 
6 
25 
88600 
125000 
213600 
Ultimately Total duration and Cost of the project is reduced to 213600 TL to 25 days from 272000 TL and 38 days respectively. Now, all critical activities A, F, G, and H are at their crash durations, no further reduction is possible, so the project has reached at optimum duration point and no other critical path is available.

Numerical problem:
The durations and direct costs for each activity in the network of a construction contract both normal and crash conditions are given in below Table. Determine the optimum duration of the contract assuming the indirect cost amounts to 125 TL / week. The normal cost, normal duration, crash duration and crash cost of a project are given below in Table 3.
TABLE 3. THE OPTIMUM (5TH) CRASHING
Act.
Pred. Act.
Normal
Crash
TAi (Week)
C (TL)
Dur. (Week)
Cost (TL)
Dur. (Week)
Cost (TL)
A
—
12
7000
10
7200
2
100
B
A
8
4000
6
5300
2
650
C
A
15
5000
12
5600
3
200
D
B
23
5000
23
5000
0
0
E
B
5
1000
4
1050
1
50
F
C
5
3000
4
3300
1
300
G
E,C
20
6000
15
6300
5
60
H
F
13
2500
11
2580
2
40
I
D,G,C
12
3000
10
3030
2
15
After performing the 5 crashing it was obtained that total duration is reduced from 59 weeks to 49 weeks and cost of the project slightly increased from 43875 TL to 43985 TL which is almost negligible, thus the project has reached at optimum duration point in 5th crashing and no other critical path is available. As indirect, direct and total project cost due to optimum crashing can be clearly seen in Table 4. Figure 5 demonstrates the total project cost vs total duration of the project at its optimum values.
TABLE 4. THE OPTIMUM (5TH) CRASHING
Cycle
Duration (weeks)
Direct Cost (TL)
Indirect Cost (TL)
Total Cost (TL)
0
59
36500
7375
43875
1
57
36620
7125
43745
2
55
36760
6875
43635
3
53
36960
6625
43585
4
51
37160
6375
43535
5
49
37860
6125
43985
Project optimal duration
50000
40000
Total cost (TL)
Total cost (TL)
30000
20000
10000
0
59 57 55 53 51 49
Duration (week)
Direct Cost (TL) Indirect Cost (TL)
Total Cost (TL)
FIG. 5 TOTAL COST VS TOTAL DURATION OF THE PROJECT

CONCLUSION
From the obtained result, it is observed that the heuristic algorithm presented in this study provide the optimal solution to all these network critical path time cost tradeoffs problems. The algorithm is single step, simple and straight forward. This was the case that, this algorithm is extensively being used to the problem of minimizing the cost of expediting activities in order to complete a project within the desired time. The network of the project is starting from an initial cost of 272000 TL at the initial stage, the optimum cost value is obtained as 213600 TL at the 6th iteration crashing, reducing 27.34%. Generally when reduction in duration occurs, total cost increases. But in this problem both of them are reduced, so it is an exceptional case.
Similarly, it can be obviously seen that the network of the project starts from an initial time duration of 59 weeks at the beginning and 49th weeks is found to be optimum time span at the 5th crashing, decreasing the project duration 10 weeks from the deadline. There is a negligible increment in the total cost of the project, though.
The result shows that although Siemens algorithm is able to optimally solve smallsized instances, Comparing with some heuristic methods i.e. memetic algorithm it has lower speed and memetic algorithm shows the higher speed than that of this proposed algorithm, because Siemens algorithm always starts searching the problem space from the right side of TimeCost curve. Therefore, when the optimum
point is placed on the left side of the curve, it takes more time to reach the optimum point.
ACKNOWLEDGMENT
This paper is the revised version of the proceeding presented in 12th International Conference on Advances in Civil Engineering (ACE Istanbul 2016) 21 23 September
2016, BoaziÃ§i, Turkey.
REFERENCES

Afshar, A., Ziaraty, A. K., Kaveh, A., & Sharifi, F. (2009). Nondominated Archiving Multi colony Ant Algorithm in Time Cost TradeOff Optimization. Journal of Construction Engineering and ManagementASCE, 135(7), 668674

Azaron A Perkgoz C and Sakawa M (2005) A genetic algorithm approach for the timecost tradeoff in PERT networks, Appl. Maths Comput. 168, 13171339.

Bell, C. E., and Han, J. (1991). A new heuristic solution method of resource constrained project scheduling problems. Naval Res. Logistics, 38, 315331.

Boctor, F. F. (1993). Heuristic for scheduling projects with resource restrictions and several resourceduration modes. Int.
J. ProductionRes., 31, 25472558.

Burns, S., Liu, L., and Feng, C. (1996). The LP/IP hybrid method for construction timecost tradeoff analysis. Constr. Mgmt. and Economics, 14, 265276.

Chassiakos, A. P., & Sakellaropoulos, S. P. (2005). Timecost optimization of construction projects with generalized activity constraints. Journal of Construction.

De, P., Dunne, E. J., and Wells, C. E. (1995). The discrete timecost tradeoff problem revisited. Eur. J. Operational Res., 81, 225238.

Elmagraby, S. E. (1993). Resource allocation via dynamic programming in activity networks. Eur. J. Operational Res., 64, 199215.

Eirgash, M.A. (2018), ParetoFront performance of multiobjective teaching learning based optimization algorithm on timecost tradeoff optimization problems, M.Sc. Dissertation, Karadeniz Technical University, Turkey.

Eirgash, M. A., and Dede, T. (2018). A multiobjective improved teaching learningbased optimization algorithm for timecost tradeoff problems. J. Constr. Eng. Manage. Innovation, 1(3), 118128.

Eshtehardian, E., Afshar, A., & Abbasnia, R. (2008). Timecost optimization: using GA and fuzzy sets theory for uncertainties in cost. Construction Management and Economics,

Eshtehardian, E., Afshar, A., & Abbasnia, R. (2008). Timecost optimization: using GA and fuzzy sets theory for uncertainties in cost. Construction Management and Economics, 26(7), 679 691.

Fondahl, J. W. (1961). A noncomputer approach to the critical path method for the construction industry. Tech. Rep. No. 9, Constr. Inst., Dept. of Civ. Engrg., Stanford University, Stanford, Calif.

Henderickson, C., and Au, T. (1989). Project management for construction. PrenticeHall, Englewood Cliffs, N.J.

Kelley, J. E. (1961). Criticalpath planning and scheduling: Mathematical basis. Oper. Res., 9(3), 296320.

Lee, K. S., Geem, Z. W., 2005, A New MetaHeuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice, Comput. Methods Appl. Mech. Engrg., Vol.194, No.1, pp. 3902 3933.

Meyer, W. L., and Shaffer, L. R. (1963). Extensions of the critical path method through the application of integer programming. Civ. Engrg. Constr. Res. Ser. 2, University of Illinois, Urbana.

Nicolai Siemens, 1971. A Simple CPM TimeCost Tradeoff Algorithm, Management Science, 17 Application Series Feb.

Robinson, D. R. (1975). A dynamic programming solution to costtime tradeoff for CPM. Mgmt. Sci., 22(2), 158166

Siemens, N. (1971). A simple CPM timecost tradeoff algorithm. Mgmt. Sci., 17(6), B354B363.

Zheng, D. X. M., & Ng, S. T. (2005). Stochastic timecost optimization model incorporating fuzzy sets theory and non replaceable front. Journal of Construction Engineering and ManagementASCE,

Zheng, D. X. M., Ng, S. T., & Kumaraswamy, M. M. (2005). Applying Pareto ranking and niche formation to genetic algorithmbased multiobjective timecost optimization. Journal of Construction Engineering and ManagementASCE,