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.  Zbl1082.65543
  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.  Zbl1111.90051
  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.  Zbl0227.90020
  5. A. Charnes, W. Cooper and G. Thompson, Critical Path Analysis via Chance Constrained and Stochastic Programming. Oper. Res.12 (1964) 460–470.  Zbl0125.09602
  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.  Zbl0125.08102
  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).  Zbl0913.90168
  9. S. Elmaghraby, On the Expected Duration of PERT Type Networks. Management Sci.13 (1967) 299–306.  Zbl0158.38303
  10. S. Elmaghraby, Resource Allocation via Dynamic Programming in Activity Networks. Eur. J. Oper. Res.64 (1993) 199–245.  Zbl0769.90049
  11. J. Falk and J. Horowitz, Critical Path Problem with Concave Cost Curves. Management Sci.19 (1972) 446–455.  Zbl0248.90057
  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.  Zbl0949.90012
  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.  Zbl1012.90004
  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.  Zbl0576.90051
  16. D. Fulkerson, A Network Flow Computation for Project Cost Curves. Management Sci.7 (1961) 167–178.  Zbl0995.90519
  17. D. Fulkerson, Expected Critical Path Lengths in PERT Networks. Oper. Res.10 (1962) 808–817.  Zbl0124.36304
  18. M. Garman, More on Conditioned Sampling in the Simulation of Stochastic Networks. Management Sci.19 (1972) 90–95.  Zbl0241.90022
  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.  Zbl0098.12103
  22. S. Kirkpatrick, J. Gelatt and M. Vecchi, Optimization by Simulated Annealing. Science220 (1983) 671–680.  Zbl1225.90162
  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.  Zbl0194.50701
  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.  Zbl0137.39302
  28. M. Neuts, Matrix-geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD (1981).  Zbl0469.60002
  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.  Zbl0324.90025
  32. D. Robinson, A Dynamic Programming Solution to Cost-Time Trade-Off for CPM. Management Sci.22 (1965) 158–166.  Zbl0313.90065
  33. S. Sethi, and G. Thompson, Optimal Control Theory. Martinus Nijhoff Publishing, Boston (1981).  Zbl0485.49002
  34. C. Sigal, A. Pritsker and J. Solberg, The Use of Cutsets in Monte-Carlo Analysis of Stochastic Networks. Mathematical Simulation21 (1979) 376–384.  Zbl0416.90030
  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.  Zbl0974.90510
  36. L. Tavares, Optimal Resource Profiles for Program Scheduling. Eur. J. Oper. Res.29 (1987) 83–90.  Zbl0615.90069
  37. J. Weglarz, Project Scheduling with Continuously Divisible Doubly Constrained Resources. Management Sci.27 (1981) 1040–1053.  Zbl0467.90033

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.