A discrete-time approximation technique for the time-cost trade-off in PERT networks
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 61-81.

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.

DOI : 10.1051/ro:2007005
Classification : 90C29, 90C35, 90C59
Mots-clés : project management, multiple objective programming, optimal control, markov processes, simulated annealing 
@article{RO_2007__41_1_61_0,
     author = {Azaron, Amir and Sakawa, Masatoshi and Tavakkoli-Moghaddam, Reza and Safaei, Nima},
     title = {A discrete-time approximation technique for the time-cost trade-off in {PERT} networks},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {61--81},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {1},
     year = {2007},
     doi = {10.1051/ro:2007005},
     mrnumber = {2310540},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2007005/}
}
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 - Recherche Opérationnelle
PY  - 2007
SP  - 61
EP  - 81
VL  - 41
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2007005/
DO  - 10.1051/ro:2007005
LA  - en
ID  - RO_2007__41_1_61_0
ER  - 
%0 Journal Article
%A Azaron, Amir
%A Sakawa, Masatoshi
%A Tavakkoli-Moghaddam, Reza
%A Safaei, Nima
%T A discrete-time approximation technique for the time-cost trade-off in PERT networks
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 61-81
%V 41
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2007005/
%R 10.1051/ro:2007005
%G en
%F RO_2007__41_1_61_0
Azaron, Amir; Sakawa, Masatoshi; Tavakkoli-Moghaddam, Reza; Safaei, Nima. A discrete-time approximation technique for the time-cost trade-off in PERT networks. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 61-81. doi : 10.1051/ro:2007005. http://archive.numdam.org/articles/10.1051/ro:2007005/

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

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

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

[5] A. Charnes, W. Cooper and G. Thompson, Critical Path Analysis via Chance Constrained and Stochastic Programming. Oper. Res. 12 (1964) 460-470. | Zbl

[6] D. Chau, W. Chan and K. Govindan, A Time-Cost Trade-Off Model with Resource Consideration Using Genetic Algorithm. Civil Engineering Systems 14 (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. | Zbl

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

[10] S. Elmaghraby, Resource Allocation via Dynamic Programming in Activity Networks. Eur. J. Oper. Res. 64 (1993) 199-245. | Zbl

[11] J. Falk and J. Horowitz, Critical Path Problem with Concave Cost Curves. Management Sci. 19 (1972) 446-455. | Zbl

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

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

[14] C. Feng, L. Liu, and S. Burns, Using Genetic Algorithms to Solve Construction Time-Cost Trade-Off Problems. J. Construction Engineering and Management, ASCE 11 (1997) 184-189.

[15] G. Fishman, Estimating Critical Path and Arc Probabilities in Stochastic Activity Networks. Naval Res. Logistic Quarterly 32 (1985) 249-261. | Zbl

[16] D. Fulkerson, A Network Flow Computation for Project Cost Curves. Management Sci. 7 (1961) 167-178. | Zbl

[17] D. Fulkerson, Expected Critical Path Lengths in PERT Networks. Oper. Res. 10 (1962) 808-817. | Zbl

[18] M. Garman, More on Conditioned Sampling in the Simulation of Stochastic Networks. Management Sci. 19 (1972) 90-95. | Zbl

[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 Economics 55 (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. | Zbl

[22] S. Kirkpatrick, J. Gelatt and M. Vecchi, Optimization by Simulated Annealing. Science 220 (1983) 671-680.

[23] C. Koulamas, S. Antony and R. Jaen, A Survey of Simulated Annealing Applications to Operations Research Problems. Omega 22 (1994) 41-56.

[24] V. Kulkarni and V. Adlakha, Markov and Markov-Regenerative PERT Networks. Oper. Res. 34 (1986) 769-781. | Zbl

[25] L. Lamberson and R. Hocking, Optimum Time Compression in Project Scheduling. Management Sci. 16 (1970) 597-606. | Zbl

[26] Z. Laslo, Activity Time-Cost Tradeoffs under Time and Cost Chance Constraints. Comput. Industrial Engineering 44 (2003) 365-384.

[27] J. Martin, Distribution of the Time Through a Directed Acyclic Network. Oper. Res. 13 (1965) 46-66. | Zbl

[28] M. Neuts, Matrix-geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD (1981). | MR | Zbl

[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 Management 18 (2000) 215-222.

[31] P. Robillard, Expected Completion Time in PERT Networks. Oper. Res. 24, (1976) 177-182. | Zbl

[32] D. Robinson, A Dynamic Programming Solution to Cost-Time Trade-Off for CPM. Management Sci. 22 (1965) 158-166. | Zbl

[33] S. Sethi, and G. Thompson, Optimal Control Theory. Martinus Nijhoff Publishing, Boston (1981). | MR | Zbl

[34] C. Sigal, A. Pritsker and J. Solberg, The Use of Cutsets in Monte-Carlo Analysis of Stochastic Networks. Mathematical Simulation 21 (1979) 376-384. | Zbl

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

[36] L. Tavares, Optimal Resource Profiles for Program Scheduling. Eur. J. Oper. Res. 29 (1987) 83-90. | Zbl

[37] J. Weglarz, Project Scheduling with Continuously Divisible Doubly Constrained Resources. Management Sci. 27 (1981) 1040-1053. | Zbl

Cité par Sources :