A discrete-time approximation technique for the time-cost trade-off in PERT networks

Amir Azaron; Masatoshi Sakawa; Reza Tavakkoli-Moghaddam; Nima Safaei

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 61-81
  • ISSN: 0399-0559

Abstract

top

We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting objective functions. Solving this optimal control problem, optimally, is impossible. Therefore, a discrete-time approximation technique is applied to solve the original multi-objective optimal control problem, using goal attainment method. To show the advantages of the proposed technique, we also develop a Simulated Annealing (SA) algorithm to solve the problem, and compare the discrete-time approximation results against the SA and also the genetic algorithm results.

How to cite

top

Azaron, Amir, et al. "A discrete-time approximation technique for the time-cost trade-off in PERT networks ." RAIRO - Operations Research 41.1 (2007): 61-81. <http://eudml.org/doc/250114>.

@article{Azaron2007,
abstract = { 
We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting objective functions. Solving this optimal control problem, optimally, is impossible. Therefore, a discrete-time approximation technique is applied to solve the original multi-objective optimal control problem, using goal attainment method. To show the advantages of the proposed technique, we also develop a Simulated Annealing (SA) algorithm to solve the problem, and compare the discrete-time approximation results against the SA and also the genetic algorithm results. },
author = {Azaron, Amir, Sakawa, Masatoshi, Tavakkoli-Moghaddam, Reza, Safaei, Nima},
journal = {RAIRO - Operations Research},
keywords = {Project management; multiple objective programming; optimal control; markov processes; simulated annealing.},
language = {eng},
month = {6},
number = {1},
pages = {61-81},
publisher = {EDP Sciences},
title = {A discrete-time approximation technique for the time-cost trade-off in PERT networks },
url = {http://eudml.org/doc/250114},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Azaron, Amir
AU - Sakawa, Masatoshi
AU - Tavakkoli-Moghaddam, Reza
AU - Safaei, Nima
TI - A discrete-time approximation technique for the time-cost trade-off in PERT networks
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 61
EP - 81
AB - 
We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting objective functions. Solving this optimal control problem, optimally, is impossible. Therefore, a discrete-time approximation technique is applied to solve the original multi-objective optimal control problem, using goal attainment method. To show the advantages of the proposed technique, we also develop a Simulated Annealing (SA) algorithm to solve the problem, and compare the discrete-time approximation results against the SA and also the genetic algorithm results.
LA - eng
KW - Project management; multiple objective programming; optimal control; markov processes; simulated annealing.
UR - http://eudml.org/doc/250114
ER -

References

top
  1. A. Azaron, C. Perkgoz and M. Sakawa, A Genetic Algorithm Approach for the Time-Cost Trade-Off in PERT Networks. Appl. Math. Comput.168 (2005) 1317–1339.  
  2. A. Azaron, H. Katagiri, M. Sakawa, K. Kato and A. Memariani, A Multi-objective Resource Allocation Problem in PERT Networks. Eur. J. Oper. Res.172 (2006) 838–854.  
  3. E. Berman, Resource Allocation in a PERT Network Under Continuous Activity Time-cost Function. Management Sci.10 (1964) 734–745.  
  4. J. Burt and M. Garman, Conditional Monte Carlo: A Simulation Technique for Stochastic Network Analysis. Management Sci.18 (1977) 207–217.  
  5. A. Charnes, W. Cooper and G. Thompson, Critical Path Analysis via Chance Constrained and Stochastic Programming. Oper. Res.12 (1964) 460–470.  
  6. D. Chau, W. Chan and K. Govindan, A Time-Cost Trade-Off Model with Resource Consideration Using Genetic Algorithm. Civil Engineering Systems14 (1997) 291–311.  
  7. C. Clingen, A Modification of Fulkerson's Algorithm for Expected Duration of a PERT Project when Activities Have Continuous d. f. Oper. Res.12 (1964) 629–632.  
  8. E. Demeulemeester, W. Herroelen and S. Elmaghraby, Optimal Procedures for the Discrete Time-Cost Trade-Off Problem in Project Networks. Research Report, Department of Applied Economics, Katholieke Universiteit Leuven, Leuven, Belgium (1993).  
  9. S. Elmaghraby, On the Expected Duration of PERT Type Networks. Management Sci.13 (1967) 299–306.  
  10. S. Elmaghraby, Resource Allocation via Dynamic Programming in Activity Networks. Eur. J. Oper. Res.64 (1993) 199–245.  
  11. J. Falk and J. Horowitz, Critical Path Problem with Concave Cost Curves. Management Sci.19 (1972) 446–455.  
  12. S. Fatemi Ghomi and S. Hashemin, A New Analytical Algorithm and Generation of Gaussian Quadrature Formula for Stochastic Network. Eur. J. Oper. Res.114 (1999) 610–625.  
  13. S. Fatemi Ghomi and M. Rabbani, A New Structural Mechanism for Reducibility of Stochastic PERT Networks. Eur. J. Oper. Res.145 (2003) 394–402.  
  14. C. Feng, L. Liu, and S. Burns, Using Genetic Algorithms to Solve Construction Time-Cost Trade-Off Problems. J. Construction Engineering and Management, ASCE11 (1997) 184–189.  
  15. G. Fishman, Estimating Critical Path and Arc Probabilities in Stochastic Activity Networks. Naval Res. Logistic Quarterly32 (1985) 249–261.  
  16. D. Fulkerson, A Network Flow Computation for Project Cost Curves. Management Sci.7 (1961) 167–178.  
  17. D. Fulkerson, Expected Critical Path Lengths in PERT Networks. Oper. Res.10 (1962) 808–817.  
  18. M. Garman, More on Conditioned Sampling in the Simulation of Stochastic Networks. Management Sci.19 (1972) 90–95.  
  19. D. Golenko-Ginzburg and A. Gonik, A Heuristic for Network Project Scheduling with Random Activity Durations Depending on the Resource Reallocation. Inter. J. Production Economics55 (1998) 149–162.  
  20. K. Gutzmann, Combinatorial Optimization Using a Continuous State Boltzmann Machine. Proceedings of IEEE First Int. Conf. Neural Networks, Vol. III, San Diego, CA (1987) 721–728.  
  21. J. Kelly, Critical Path Planning and Scheduling: Mathematical Basis. Oper. Res.9 (1961) 296–320.  
  22. S. Kirkpatrick, J. Gelatt and M. Vecchi, Optimization by Simulated Annealing. Science220 (1983) 671–680.  
  23. C. Koulamas, S. Antony and R. Jaen, A Survey of Simulated Annealing Applications to Operations Research Problems. Omega22 (1994) 41–56.  
  24. V. Kulkarni and V. Adlakha, Markov and Markov-Regenerative PERT Networks. Oper. Res.34 (1986) 769–781.  
  25. L. Lamberson and R. Hocking, Optimum Time Compression in Project Scheduling. Management Sci.16 (1970) 597–606.  
  26. Z. Laslo, Activity Time-Cost Tradeoffs under Time and Cost Chance Constraints. Comput. Industrial Engineering44 (2003) 365–384.  
  27. J. Martin, Distribution of the Time Through a Directed Acyclic Network. Oper. Res.13 (1965) 46–66.  
  28. M. Neuts, Matrix-geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD (1981).  
  29. C. Perry, I. Creig, Estimating the Mean and Variance of Subjective Distributions in PERT and Decision Analysis. Management Sci.21 (1975) 1477–1480.  
  30. P. Pontrandolfo, Project Duration in Stochastic Networks by the PERT-Path Technique. Inter. J. Project Management18 (2000) 215–222.  
  31. P. Robillard, Expected Completion Time in PERT Networks. Oper. Res.24, (1976) 177–182.  
  32. D. Robinson, A Dynamic Programming Solution to Cost-Time Trade-Off for CPM. Management Sci.22 (1965) 158–166.  
  33. S. Sethi, and G. Thompson, Optimal Control Theory. Martinus Nijhoff Publishing, Boston (1981).  
  34. C. Sigal, A. Pritsker and J. Solberg, The Use of Cutsets in Monte-Carlo Analysis of Stochastic Networks. Mathematical Simulation21 (1979) 376–384.  
  35. C. Schmit, and I. Grossmann, The Exact Overall Time Distribution of a Project with Uncertain Task Durations. Eur. J. Oper. Res.126 (2000) 614–636.  
  36. L. Tavares, Optimal Resource Profiles for Program Scheduling. Eur. J. Oper. Res.29 (1987) 83–90.  
  37. J. Weglarz, Project Scheduling with Continuously Divisible Doubly Constrained Resources. Management Sci.27 (1981) 1040–1053.  

NotesEmbed ?

top

You must be logged in to post comments.