### Paper Menu >>

### Journal Menu >>

Engineering, 2009, 1, 1-54 Published Online June 2009 in SciRes (http://www.SciRP.org/journal/eng/). Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 The Effect of Price Discount on T ime-Cost Trade-off Problem Using Genetic Algorithm Hadi Mokhtari1, Abdollah Aghaie2 Industrial Engineering Department, K. N. Toosi University of Technology, Tehran, Iran Email: 1Mokhtari_IE@yahoo.com, 2AAghaie@kntu.ac.ir Received April 21, 2009; revised May 13, 2009; accepted May 18, 2009 Abstract Time-cost trade off problem (TCTP), known in the literature as project crashing problem (PCP) and project speeding up problem (PSP) is a part of project management in planning phase. In this problem, determining the optimal levels of activity durations and activity costs which satisfy the project goal(s), leads to a balance between the project completion time and the project total cost. A large amount of literature has studied this problem under various behavior of cost function. But, in all of them, influence of discount has not been in- vestigated. Hence, in this paper, TCTP would be studied considering the influence of discount on the re- source price, using genetic algorithm (GA). The performance of proposed idea has been teste d on a medium scale test problem and several computational experiments have been conducted to investigate the appropriate levels of proposed GA considering accuracy and computational time. Keywords: Project Management, PERT Networks, Time Cost Trade off, Genetic Algorithm, Discount 1. Introduction Time-cost trade off problem (TCTP) is an important part of the project management in planning phase. It is a sub problem of project scheduling when finding the most cost effective way to finish a project within time limit is desirable. In the TCTP, the objective is to determine the duration of each activity in o rder to obtain the minimum costs of the proj ect. All existing patterns of this problem satisfy the objective function through expediting the activity durations. In this problem, determining the opti- mal levels of activity d ur ations and activ ity costs leads to a balance between the project completion time and the project total cost. There are some procedures in TCTP (e.g. extra resource allocation, improvement in technol- ogy level, increase in the quality of materials, hiring highly skillful human resou rces, etc.) used for expeditin g the activity durations, according to activity characteris- tics. These procedures can be summarized to a unique cost function corresp onding to each activity. Herroelen and Leus [1] evaluated some stochastic models of the TCTP under two main categories: “The stochastic discrete time/cost trade-off problem” and “Multi-mode trade-off problem in stochastic networks”. In the stochastic TCTP, when objective function of the model is related to the time, Bowman [2] presents a heuristic algorithm based on simulation technique and solves a general project compression problem using the derivative estimators. Besides, the application of mathe- matical programming for the stochastic project crashing problem was suggested by Abbasi and Mukattash [3], in which activities are assumed to have three time estimates. Unfortunately, it seems that the proposed approach has been developed for a network with a single path and is not applicable for the ne tworks with slight differences in the path durations. Arisawa and Elmaghraby [4] sug- gested the use of fractional linear programming for the optimal allocation of resources to the activities in order to maximize the reduction in project mean duration per unit investment in GERT type networks. A novel re- source-constrained project scheduling problem has been modeled by Golenko and Gonik [5] as a knapsack re- 34 H. MOKHTA RI ET AL. Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 source reallocation problem in which a heuristic algo- rithm has been to determine the optimal amount of re- sources allocated to the activities and their start times. Some authors have investigated the stochastic TCTP to minimize the project total costs [6-8]. Gutjahr et al. [9] studied the discrete model of this problem by using the stochastic branch and bound method to improve the probability of meeting project deadline. In their work, they assumed that the crashing of activity durations (by using additional costs) leads to higher direct costs and lower penalty costs. In another research, Mitchell and Klastorin [10] have formulated the objective function with the direct, indirect, and penalty costs. This study presents a Stochastic Compression Project (SCOP) heu- ristic based on decomposition of PERT networks into th e serial and parallel subnets. Recently, some researchers have considered the multi criteria/objective formulation for the stochastic TCTP [11-14]. In all of the presented papers, TCTP have investig ated under various behaviors of the cost function such as discrete cost function [5,15-19], linear continuous cost function [20-22], nonlinear convex cost function [23,24], nonlinear concave cost function [25] and linear piece- wise cost function [26,27]. But, in all of them, influence of discount has not been investigated. In this study, we develop a new TCTP based on discoun t in resource price to maximize the project completion probability in a pre- defined deadline using a limited available budget. In order to construct the model we assume that activity durations follow the normal distribution and the activity mean durations represent the decision variables. In order to solve this problem, we organize the genetic algorithm (GA) technique. Recently, some researchers use the GA in order to solv e the project scheduling problems such as TCTP [11]. This paper is organized in the following way. The mathematical model is presented in Section 2. Section 3 describes the structure of the proposed approach, which is based on the GA algorithm. The characteristics of a large scale numerical example and results of applying the proposed approach to that example are presented in Sec- tion 4. The appropriate levels of GA parameters are in- vestigated in this section. Finally Section 5 consists of concluding remarks. 2. Mathematical Model Let be an acyclic Activity on Arrow ((,)GNA A OA ) graph with arrow set and node set, where the source and sink node are denoted by AN s and t , respectively. 12 ( ,,...,) m Nnn n represents the set of events, 12 ( ,,...,) n A aa a represents the set of activities in a project PERT netw or k wi t h m nodes andn activities. Considered notation s are presented as follows: (, )ij ij t ij Activity with i head node and j tail node Random variable of activity (i, j) duration Mean duration of activity (i, j) (decisionvariable) ij Standard deviation of activity (i, j) ij CS ij R d T u ij Cost slope of activity (i, j) Amount of allocated resource to activity (i, j) Project completion deadline Upper limit of mean of ith activity. l ij Lower limit of mean of ith activity. M Total number of paths. Amount of available budget (i, j). L r n r T r Number of activities which lie on path r. Random variable of path r duration. The mean duration of path r. r The standard deviation of path r. Cumulative distribution function (CDF) ofnormal standard distribution. Generally, the TCTP is a nonlinear optimization prob- lem. In order to investigate the effect of discount on this problem, we extract the objective function (project com- pletion probability) and constraints, separately. The ob- jective function (OF) is concerned with the maximization of project completion probability. To construct the OF, we can write a single path completion probability ac- cording to the central limit theo rem (CLT), in the fo llow- ing way: rij rij rij ij rij ijd ij d r TT Z r Pr ij d dr T ZTT PrPr (1) Equation (1) is related to a single path and can’t im- prove the total project completion probability. Thus, considering all of the paths, the following objective fun c- tion is suggested: },r rijij rijij 2,1{ T MinMax d ,.. L.. (2) Two type of restrictions should be modeled in a mathematical formulation to ensure the obtained solu- H. MOKHTARI ET AL. 35 Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 Using (4) we can formulate the cost function for activ- ity as a mathematical representation, in the following way: ),(ji tions satisfy the budget limitation and real conditions. Each activity can be planned between two maximum and minimum limit of its mean duration. Following mathe- matical representation show this type of constraint: (4) min 1 11 2 22 3 11 max .. .. .. ijijij ij ijij ijij ijij ijij ij kk ijijij ij kk ijij ijij SRRR SRRR SRRR CS SRRR SRRR (3) u ijij l ij It is assumed that each activity needs a unique type of resource. Using this assumption, in order to model the budget limitation, we can define the effect of discount on resource price in a mathematical representation. For this purpose, cost slope (CS) due to various levels of ij is presented below: k M max max () 1 max11 1 ()()() () 1 min 1(mi max1minmin 1min ()()( ) 1 Sijijij ij ij ij nkkk nnnn SSS ij ijij ijij ijijij ijijij ij Cij ijk kk k SS ij ijij ijij ijijijijijijij k s n) 1 (5) Using (4) and (5), we can formulate the second con- straint that satisfies budget limitation, in the following way: model help us to use the available extra budget more efficiently, when we could find suppliers with discount policies. (6) ()C ij ij 3. Applying Genetic Algorithm So, the proposed TCTP can be summarized as a nonlinear optimization model, as follows: Genetic Algorithm (GA) is one of the popular metaheu- ristic algorithms, which can explore the feasible space using computational intelligence inspired from natural genetics and evolutionary concepts. It is a search method based on random selection policy can be used to solve the nonlinear mathematical programs. In this technique, an initial populatio n containing several feasib le solutions (chromosome) is generated randomly. Interesting fact is that GA does not need a good initial solution. In this procedure, algorithm starts from an initial solution and then it would be improved through an evolutionary proc- ess. After production of initial randomly generated popu - lation, parents are selected from this primary population and produce offspring. Second population is a combina- tion of parent and offspring. The generation procedure has been done using two effective operators, cross over and mutation. The crossover is a genetic operator used to vary the programming of a chromosome or chromo- somes from one generation to the next and the mutation operator can prevent th e premature convergence of a new {1,2,...., } Tdij ij r M ax MinrL ij ij r (7) Subject to: () ,C ij ij M (8) lu A ctivitiy ijr ijijij (9) This is a new formulation of TCTP in PERT networks. In order to shorten each activity, some amount of extra resources is needed. This amount of resources may be provided by external su ppliers, who may determine some incentive policy such as price discount. Our proposed TCTP, models this situation. Using this model, project manager can increase confidence level of on-time project completion and prevent project delay. Also, proposed 36 H. MOKHTA RI ET AL. Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 generation [28]. Desirability of obtained offspring is investigated using fitness function which is concerned with objective function and feasibility. The most com- mon steps for GA follow: Generate the initial population Evaluate the fitness of all solutions in popula- tion Repeat: Select parents Apply the cross over and mutation operators to produce children Evaluate the fitness of children Establish new population using a combination of parents and children Until a satisfactory solution has been obtained About the proposed GA for the discount based TCTP, we develop the chromosome structure as a simple string of decision variables. Indeed, each chromosome repre- sents ij for all of the activities. Proposed GA algorithm steps are presented in the fo llowing way: Initial random population is generated using uniform random number generator. Fitness of individuals is evaluated. Population is ranked in terms of computed fit ness. Parents are selected randomly. Cross over and mutation are applied to produce children. Produced offspring are evaluated using fitness function. Form the new population using half of the fit- test parent and half of the fittest children . About the fitness function some points should be men- tioned. In order to evaluate a solution (chromosome), two parameter should be investigated, goodness of solu- tion and meaningfulness of solution. The goodness is concerned with objective function (project completion probability) and the meaningfulness indicates the feasi- bility. According to these parameters the fitness function can be represented as follows: 1, 2,..., Tdij ij r F itness FunctionMinrL ij ij ij projectij r (10) In which, the first term represents feasibility and sec- ond one is concerned with project completion probability. ij would be equal to one, ifl ijij iju & and otherwise, indicates zero. ()C ij ij M 4. Numerical Example In order to investigate the performance of the presented GA approach for the proposed discount based model of stochastic TCTP, a numerical example are described in this section. We conducted the proposed approach for the large scale example with 15 nodes, 20 independent ac- tivities and 44 interrelated paths to show that how the presented approach optimally improves the project com- pletion probability. Characteristics of this network are presented in Table 2. The objective is to obtain optimal allocated budget to the activities in order to improve the all path completion probability from a risky value to a maximum confident one. It is assumed that the time unit is in weeks and the co st is in thousan d dollars. Accord ing to the presented characteristics, initial probability of the project completion time at Td =150 which can be com- uted by using the Central Limit Theorem (CLT) is equal to 55%. This value is related to a situ ation that all activi- ties are planned in their upper bound of p ij . The pro- posed approach attempts to improve this value to a maximum level using the limited available budget in order to decrease the risk of project tardiness. It is also assumed that the available amount of additional budget for this purpose is equal to 10,000 thousand dollars. We conducted our analysis of the presented example in two steps. In first step we run the developed procedure with the random initial values for parameters of the proposed GA. Then the obtained results are considered to deter- mine the efficient values of the parameters in terms of the accuracy and computation time. For this purpose we developed a computer simulation program based on the proposed approach and randomly initial values of GA parameters have been considered in primary computa- tional effort. The obtained simulatio n results for the con- sidered ex ample are organized in Table 1. To investigate efficiency of the proposed GA ap- proach, best obtained project completion probability and CPU time have been considered. In order to make trade off between the accuracy and computation time, we also solve the example with the different values of popula- tion size (k), mutation and cross over probabilities, then H. MOKHTARI ET AL. 37 Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 Table 1. Characteristics of considered example. compute thecomputation time and efficiency measure. The appropriate levels of these parameters can conduct the GA toward optimal solution, directly and therefore, the analysis of these parameters is an important aspect of the proposed GA approach. Tables 2, 3 and 4 provide the behavior of the model results according to different lev- els of parameters, for presented example. According to the simulation results provided by Tables 2, 3 and 4 the best prob ability of cross over and mutation rates are 0.8 and 0.2, respectively and best values of considered criteria (accuracy and CPU time) obtained by setting population size at 25-30. In this example the project completion probability has been improved from 55% to 0.79%. 5. Model Validation The appropriate levels of the GA parameters have been investigated in section 4 to reach the accurate results with reasonable computation time. By using this proce- dure we reach the maximum capabilities of the proposed GA approach in terms of accuracy and computational time, but these maximum capabilities should be compared Table 2. Model results (objective function) for different levels of (k = 25). c P,2.0 m P c P Run 1* Run 2 Run 3 Run 4 Best Obj. 0.1 0.73900.71420.6952 0.7202 0.7390 0.2 0.69660.64140.7157 0.7377 0.7377 0.4 0.72220.61970.7585 0.6726 0.7585 0.6 0.72470.62530.7822 0.6792 0.7822 0.8 0.70090.69570.7951 0.7823 0.7951 * Each runs containing 200 iterations Table 3. Model results (objective function) for different levels of (k = 25). m P,7.0 c P m PRun 1 Run 2 Run 3 Run 4 Best Obj. 0.10.71080.75610.6970 0.7896 0.7896 0.20.68760.78570.7952 0.7396 0.7952 0.40.71850.69690.7355 0.7291 0.7355 0.60.68270.68730.6269 0.7565 0.7565 0.80.70070.70670.7477 0.6900 0.7477 Activity l ij 1 ij ij u ij 2 ij S 1 ij S ij S ij 1 8.51 12.32 13.29 14.26 201.59 250.00 265.95 0.25 2 11.60 - 14.56 16.70 - 195.25 225.45 0.60 3 9.56 - 10.05 15.09 - 302.70 321.28 0.45 4 12.95 15.29 16.09 17.77 259.30 295.52 305.04 0.15 5 11.72 12.56 14.05 16.79 252.27 265.33 294.37 0.51 6 11.14 13.00 15.25 16.34 257.84 301.04 326.65 0.67 7 10.43 - 12.05 15.77 - 254.05 295.73 0.65 8 13.43 14.59 17.05 18.15 194.51 201.36 254.00 0.41 9 13.03 15.05 16.32 17.83 241.08 259.32 294.21 0.62 10 12.61 - 15.02 17.50 - 201.51 285.54 0.57 11 9.46 10.25 12.98 15.01 199.65 209.21 225.31 0.14 12 13.22 - 16.02 17.99 - 295.84 309.74 0.03 13 12.41 - 17.02 17.34 - 229.74 276.48 0.24 14 11.32 - 15.25 16.48 - 207.97 257.54 0.10 15 10.17 14.52 15.02 15.57 154.95 174.04 198.74 0.58 16 8.58 10.21 14.09 14.32 174.00 198.32 254.13 0.36 17 9.00 - 12.06 14.65 - 205.27 211.37 0.50 18 10.50 11.65 14.21 15.84 298.57 314.45 365.36 0.25 19 9.31 - 14.09 14.89 - 302.12 341.91 0.17 20 9.41 11.64 13.92 14.97 157.37 164.18 187.47 0.63 38 H. MOKHTA RI ET AL. Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 Table 4. Model results (computational time, objective function) for different levels of k (). 0.7,P c0.2Pm with other standard solutions which are available in the literature to validate the solution. Since, this paper is the first combination of price discount with the TCTP, there isn’t any standard test problem for the proposed model, in the published literature. We use the global optimum solution obtain ed by LINGO software to evalu- ate the performance of proposed approach. Indeed, LINGO can handle nonlinear programming problems involving bo th continuous and binary variables and solve such problem by generalized reduced gradient (GRG). For this purpose a mathematical model based on a sin- gle path of PERT network has been considered. The results of comparing the proposed GA’s best objective function (obtained by appropriate levels of GA parame- ters based on the procedure described in section 4) and LINGO’s global optimu m for a single path are presented in Ta ble 5. According to the Table 5, the proposed GA approach shows a difference with LINGO’s global optimum with the average of 1.84%. Such a little difference can be reliable and shows the good performance of proposed approach. 6. Conclusions In this paper, we proposed a new approach based on price discount for TCTP in PERT networks in which activity durations follow the normal distribution. The main objective o f the developed model is to improve the Table 5. Comparing the proposed GA best objective function and LINGO’s global optimum. Run 1 Run 2 Run 3 Run 4 k CPU time Obj. Func. CPU Time Obj. Func.CPU Time Obj. Func.CPU Time Obj. Func. CPU T ime Best Obj. 5 10.40 0.692 11.24 0.642 9.80 0.716 15.590.701 10.40 0.716 10 16.10 0.722 15.92 0.707 25.21 0.757 20.650.740 15.92 0.757 12 17.41 0.710 16.10 0.735 29.51 0.740 23.620.727 16.10 0.740 18 30.60 0.731 29.25 0.765 39.74 0.788 45.410.751 29.25 0.788 25 40.25 0.758 45.62 0.761 54.30 0.780 42.200.796 40.25 0.796 30 51.50 0.793 47.26 0.757 59.20 0.798 65.200.795 47.26 0.798 Problem Limited Budget (M) Proposed GALINGODifferences (LINGO-GA) % Differences 1 10,000 0.7425 0.7489 0.0064 0.8620 2 15,000 0.7689 0.7909 0.0220 2.8612 3 20,000 0.7849 0.7981 0.0132 1.6817 4 25,000 0.8001 0.8214 0.0213 2.6622 5 30,000 0.8149 0.8236 0.0087 1.0676 6 35,000 0.8311 0.8544 0.0233 2.8035 7 40,000 0.864 0.8764 0.0124 1.4352 8 60,000 0.9049 0.9171 0.0122 1.3482 Average 1.8402 % H. MOKHTARI ET AL. 39 Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 project completion probability from a risky amount to a maximum value using limited additional budget. To our knowledge, this is the first combination of price discount as a supplier’s policy, with the TCTP, in the published literature. The presented model determines the optimal additional resources should be allocated to activities using the genetic algorithm. The GA algorithm has or- ganized to allocate the available budget to activities. In order to illustrate the model efficiency, a computer pro- gram using MATLAB 7.6.0 was developed and the model was tested on a medium scale PERT network. Best amount of objective function and CPU time have been recorded and efficient levels of GA parameters have been investigated through the several computational experi- ments. In order to validate the GA approach, proposed model have been compared with the LINGO’s global optimum solution and obtained results showed the good performance of the proposed solution approach. 7. References [1] W. Herroelen and R. Leus, “Project scheduling under uncertainty: Survey and research potentials,” European Journal of Operational Research, Vol. 165, pp. 289–306, 2005. [2] R. A. Bowman, “Stochastic gradient-based time-cost tradeoffs in PERT networks using simulation,” Annals of Operations Research, Vol. 53, pp. 533–551, 1994. [3] G. Abbasi and A. M. Mukattash, “Crashing PERT networks using mathematical programming,” International Journal o f Project Management, Vol. 19, pp. 181–188, 2001. [4] S. Arisawa and S. E. Elmaghraby, “Optimal time-cost trade-offs in GERT networks,” Management Science, Vol. 18, pp. 589–599, 1972. [5] L. V. Tavares, “A multi stage non-deterministic model for a project scheduling under resource consideration,” Euro- pean Journal of Operational Research, Vol. 49, pp. 92– 101, 1990. [6] R. L. Bergman, “A heuristic procedure for solving the dynamic probabilistic project expediting problem,” Euro- pean Journal of Operational Research, Vol. 192, pp. 125– 137, 2009. [7] S. Foldes and F. Soumis, “PERT and crashing revisited: Mathematical generalization,” European Journal of Op- erational Research, Vol. 64, pp. 286–294, 1993. [8] L. Sunde and S. Lichtenberg, “Net-present value cost/ time trade off,” International Journal of Project Manage- ment, Vol. 13, pp. 45–49, 1995. [9] W. J. Gutjahr, C. Strauss and E. Wagner, “A stochastic branch-and-bound approach to activity crashing in project management,” INFORMS Journal on Computing, Vol. 12, pp. 125–135, 2000. [10] G. Mitchell and T. Klastorin, “An effective methodology for the stochastic project compression problem,” IIE Transaction, Vol. 39, pp. 957–969, 2007. [11] A. Azaron, C. Perkgoz, and M. Sakawa, “A genetic algo- rithm approach for the time-cost trade-off in PERT net- works,” Applied Mathematics and Computation, Vol. 168, pp. 1317–1339, 2005. [12] A. Azaron and R. Tavakkoli-Moghaddam, “A multi objective resource allocation problem in dynamic PERT networks,” Applied Mathematics and Computation, Vol. 18, pp. 163–174, 2006. [13] A. Azaron, H. Katagiri, and M. Sakawa, “Time-cost trade-off via optimal control theory in Markov PERT net- works,” Annals of Operations Research, Vol. 150, pp. 47– 64, 2007. [14] P. C. Godinho and J. P. Costa, “A stochastic multimode model for time cost tradeoffs under management flexibil- ity,” OR Spectrum, Vol. 29, pp. 311–334, 2007. [15] W. Crowston and G. L. Thompson, “Decision CPM: A method for simultaneous planning, scheduling, and con- trol of projects,” Operations Research, Vol. 15, pp. 407– 426, 1967. [16] E. Demeulemeester, S. E. Elmaghraby, and W. Herroelen, “Optimal procedures for the discrete time/cost trade-off problem in project networks,” European Journal of Op- erational Research, Vol. 88, pp. 50–68, 1996. [17] E. Demeulemeester, B. De Reyck, B. Foubert, W. Herroe- len, and M. Vanhoucke, “New computational results on the discrete time/cost trade-off problem in project net- works,” Journal of the Operational Research Society, Vol. 49, pp. 1153–1163, 1998. [18] D. R. Robinson, “A dynamic programming solution to cost-time tradeoff for CPM,” Management Science, Vol. 22, pp. 158–166, 1975. [19] M. Vanhoucke and D. Debels, “The discrete time/cost trade-off problem: Extensions and heuristic procedures,” Journal of Scheduling, Vol. 10, pp. 311–326, 2007. [20] I. Cohen, B. Golany, and A. Shtub, “The stochastic time– cost tradeoff problem: a robust optimization approach,” Networks, Vol. 49, pp. 175–188, 2007. [21] D. R. Fulkerson, “A network flow computation for pro- ject cost curves,” Management Science, Vol. 7, pp. 167– 178, 1961. [22] P. S. Pulat and S. J. Horn, “Time-resource tradeoff prob- lem,” IEEE Transactions on Engineering Management, 40 H. MOKHTA RI ET AL. Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54 Vol. 43, pp. 411–417, 1996. [23] E. B. Berman, “Resource allocation in PERT network under activity continuous time-cost functions,” Manage- ment Science, Vol. 10, pp. 734–745, 1964. [24] R. Lamberson and R. R. Hocking, “Optimum time com- pression in project scheduling,” Management Science, Vol. 16, pp. B597–B606, 1970. [25] J. Falk and J. Horowitz, “Critical path problems with concave cost-time curves,” Management Science, Vol. 19, pp. 446–455, 1972. [26] R. Kelley, “Critical-pathplanning and scheduling: Mathe- matical basis,” Operations Research, Vol. 9, pp. 296–320, 1961. [27] P. Vrat and C. Kriengkrairut, “A goal programming model for project crashing with piecewise linear time-cost trade- off,” Engineering Costs and Production Economics, Vol. 10, pp. 161–172, 1986. [28] I. Kaya, “A genetic algorithm approach to determine the sample size for control charts with variables and attrib- utes,” Expert Systems with Applications, Vol. 36, pp. 8719–8734, 2009. |