Application of Siemens’s Effective Cost Slope Approach on Time-Cost Trade-Off Optimization Problems

Application of Siemenss Effective Cost Slope Approach on Time-Cost Trade-Off Optimization Problems

Yusuf Baltaci, Mohammad Azim Eirgash Ph.D. Candidate Karadeniz Technical University Department of Civil Engineering

Turkey Trabzon. 61000

Abstract: – Timecost trade-off (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 fast-tracking 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 trade-off 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 time-cost trade-off. 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 decision-makers in concurrently arriving at an optimal project duration and total cost as well. .

Keywords Time Cost Tradeoff; Fast-Tracking; 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 time-cost alternatives and is known as time-cost trade-off problem in the literature. Moreover, timecost trade-off 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, time-cost trade-off 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 NDS-TLBO 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 time-cost trade-off 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 TIME-COST RELATIONSHIP IN PROJECTS

1. Time-cost 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.

2. Project Crashing

   Project crashing problem is primarily concerned with the trade-off 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.

3. 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.

1. 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.

   1. Siemens algorithm

      Siemens algorithm is defined as follows:

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

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

      3. 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.

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

      5. 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,

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

         2. Choose the activity with the largest necessary reduction time.

         3. Randomly choose one of the activities.

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

         1. The reducible time of the activity, TAi.

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

      7. 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.

   2. 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 Cost-Indirect 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.

   3. 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. A-F-G-H 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

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

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 38-2 =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

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

   Crash – 3

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

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 trade-off 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

5. Again activity A can be reduced from 12 days to 10 days, and project duration will reduce to 30-2 = 28 days and also total cost becomes = Dc + Cc + IDc for 28 = 226000 TL

   Crash – 6

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

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.

1. 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

2. 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 small-sized 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 Time-Cost 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

1. Afshar, A., Ziaraty, A. K., Kaveh, A., & Sharifi, F. (2009). Nondominated Archiving Multi colony Ant Algorithm in Time- Cost Trade-Off Optimization. Journal of Construction Engineering and Management-ASCE, 135(7), 668-674

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

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

4. Boctor, F. F. (1993). Heuristic for scheduling projects with resource restrictions and several resource-duration modes. Int.

   J. ProductionRes., 31, 25472558.

5. Burns, S., Liu, L., and Feng, C. (1996). The LP/IP hybrid method for construction time-cost trade-off analysis. Constr. Mgmt. and Economics, 14, 265276.

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

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

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

9. Eirgash, M.A. (2018), Pareto-Front performance of multiobjective teaching learning based optimization algorithm on time-cost trade-off optimization problems, M.Sc. Dissertation, Karadeniz Technical University, Turkey.

10. Eirgash, M. A., and Dede, T. (2018). A multi-objective improved teaching learning-based optimization algorithm for time-cost trade-off problems. J. Constr. Eng. Manage. Innovation, 1(3), 118-128.

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

12. 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.

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

14. Henderickson, C., and Au, T. (1989). Project management for construction. Prentice-Hall, Englewood Cliffs, N.J.

15. Kelley, J. E. (1961). Critical-path planning and scheduling: Mathematical basis. Oper. Res., 9(3), 296320.

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

17. 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.

18. Nicolai Siemens, 1971. A Simple CPM Time-Cost Tradeoff Algorithm, Management Science, 17 Application Series Feb.

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

20. Siemens, N. (1971). A simple CPM time-cost tradeoff algorithm. Mgmt. Sci., 17(6), B-354B-363.

21. Zheng, D. X. M., & Ng, S. T. (2005). Stochastic time-cost optimization model incorporating fuzzy sets theory and non- replaceable front. Journal of Construction Engineering and Management-ASCE,

22. Zheng, D. X. M., Ng, S. T., & Kumaraswamy, M. M. (2005). Applying Pareto ranking and niche formation to genetic algorithm-based multiobjective time-cost optimization. Journal of Construction Engineering and Management-ASCE,