Full Text:   <2659>

CLC number: C935; F205

On-line Access: 2010-06-02

Received: 2009-10-22

Revision Accepted: 2009-12-07

Crosschecked: 2010-05-14

Cited: 1

Clicked: 7347

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2010 Vol.11 No.6 P.481-494


Economic optimization of resource-constrained project scheduling: a two-phase metaheuristic approach

Author(s):  Angela H. L. Chen, Chiuh-Cheng Chyu

Affiliation(s):  Department of Industrial Engineering and Management, Yuan Ze University, Taiwan 320, Taoyuan, Department of Finance, Nanya Institute of Technology, Taiwan 320, Taoyuan

Corresponding email(s):   angela@saturn.yzu.edu.tw

Key Words:  Memetic algorithm (MA), Branch and bound (B&, B) algorithm, Net present value (NPV), Project scheduling problem

Share this article to: More <<< Previous Article|

Angela H. L. Chen, Chiuh-Cheng Chyu. Economic optimization of resource-constrained project scheduling: a two-phase metaheuristic approach[J]. Journal of Zhejiang University Science C, 2010, 11(6): 481-494.

@article{title="Economic optimization of resource-constrained project scheduling: a two-phase metaheuristic approach",
author="Angela H. L. Chen, Chiuh-Cheng Chyu",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Economic optimization of resource-constrained project scheduling: a two-phase metaheuristic approach
%A Angela H. L. Chen
%A Chiuh-Cheng Chyu
%J Journal of Zhejiang University SCIENCE C
%V 11
%N 6
%P 481-494
%@ 1869-1951
%D 2010
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C0910633

T1 - Economic optimization of resource-constrained project scheduling: a two-phase metaheuristic approach
A1 - Angela H. L. Chen
A1 - Chiuh-Cheng Chyu
J0 - Journal of Zhejiang University Science C
VL - 11
IS - 6
SP - 481
EP - 494
%@ 1869-1951
Y1 - 2010
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C0910633

This paper deals with the problem of project scheduling subject to multiple execution modes with non-renewable resources, and a model that handles some of monetary issues in real world applications. The objective is to schedule the activities to maximize the expected net present value (NPV) of the project, taking into account the activity costs, the activity durations, and the cash flows generated by successfully completing an activity. Owing to the combinatorial nature of this problem, the current study develops a hybrid of branch-and-bound procedure and memetic algorithm to enhance both mode assignment and activity scheduling. Modifications for the makespan minimization problem have been made through a set of benchmark problem instances. Algorithmic performance is rated on the maximization of the project NPV and computational results show that the two-phase hybrid metaheuristic performs competitively for all instances of different problem sizes.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Alcaraz, J., Maroto, C., 2001. A robust genetic algorithm for resource allocation in project scheduling. Ann. Oper. Res., 102(1-4):83-109.

[2]Boctor, F.F., 1993. Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res., 31(11):2547-2558.

[3]Buddhakulsomsiri, J., Kim, D.S., 2007. Priority rule-based heuristic for multi-mode resource constrained project scheduling problems with resource vacations and activity splitting. Eur. J. Oper. Res., 178(2):374-390.

[4]Chen, A.H.L., Chyu, C.C., 2007. On Maximizing the Net Present Value of a Project: a Comparison of Mode Selection Rules and Activity Priority Rules. Proc. Conf. of the Operations Research Society of Taiwan, No. 7040615967.

[5]Chen, A.H.L., Chyu, C.C., 2008. A Memetic Algorithm for Maximizing Net Present Value in Resource-Constrained Project Scheduling Problem. Proc. IEEE Congress on Evolutionary Computation, p.2401-2408.

[6]Davis, E.W., Patterson, J.H., 1975. A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Manag. Sci., 21(8):944-955.

[7]Dayanand, N., Padman, R., 1997. On modeling payments in projects. J. Oper. Res. Soc., 48(9):906-918.

[8]de Reyck, B., Leus, R., 2008. R&D project scheduling when activities may fail. IIE Trans., 40(4):367-384.

[9]Digalakis, J., Margaritis, K., 2004. Performance comparison of memetic algorithms. Appl. Math. Comput., 158(1):237-252.

[10]Doersch, R.H., Patterson, J.H., 1977. Scheduling a project to maximize its present value: a zero-one programming approach. Manag. Sci., 23(8):882-889.

[11]Elmaghraby, S.E., Herroelen, W.S., 1990. The scheduling of activities to maximize the net present value of projects. Eur. J. Oper. Res., 49(1):35-49.

[12]Etgar, R., Shtub, A., LeBlanc, L.J., 1997. Scheduling projects to maximize net present value: the case of time-dependent, contingent cash flows. Eur. J. Oper. Res., 96(1):90-96.

[13]Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, p.412.

[14]Grinold, R.C., 1972. The payment scheduling problem. Nav. Res. Log. Q., 19(1):123-136.

[15]Herroelen, W.S., Gallens, E., 1993. Computational experience with an optimal procedure for the scheduling of activities to maximize the net present value. Eur. J. Oper. Res., 65(2):274-277.

[16]Holland, J.H., 1975. Adaptation in Natural and Artificial Systems. University Michigan Press, Ann Arbor, MI, p.90-109.

[17]Icmeli, O., Erengüç, S.S., 1996. A branch-and-bound procedure for the resource-constrained project scheduling problem with discounted cash flows. Manag. Sci., 42(10):1395-1408.

[18]Klein, R., 2000. Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. Eur. J. Oper. Res., 127(3):619-638.

[19]Kolisch, R., 1996a. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur. J. Oper. Res., 90(2):320-333.

[20]Kolisch, R., 1996b. Efficient priority rules for the resource-constrained project scheduling problem. J. Oper. Manag., 14(3):179-192.

[21]Kolisch, R., Sprecher, A., Drexl, A., 1995. Characterization and generation of a general class of resource-constrained project scheduling problems. Manag. Sci., 41(10):1693-1703.

[22]Krasnogor, N., Smith, J., 2000. A Memetic Algorithm with Self-Adaptive Local Search: TSP as a Case Study. Proc. Genetic and Evolutionary Computation Conf., p.987-994.

[23]Merz, P., Freisleben, B., 2001. Memetic algorithms for the traveling salesman problem. Compl. Syst., 13(4):297-345.

[24]Michalewicz, E., 1996. Genetic Algorithms + Data Structures = Evolution Programs (3rd Ed.). Springer-Verlag, Berlin, p.15-22.

[25]Moscato, P., Norman, M.G., 1992. A ‘Memetic’ Approach for the Traveling Salesman Problem: Implementation of Computational Ecology on Message Passing Systems. In: Valero, M., Onate, E., Jane, M., et al. (Eds.), Parallel Computing and Transputer Applications. IOS Press, Amsterdam, p.187-194.

[26]Padman, R., Smith-Daniels, D.E., Smith-Daniels, V.L., 1997. Heuristic scheduling of resource-constrained projects with cash flows. Nav. Res. Log., 44(4):365-381.

[27]Patterson, J.H., Slowinski, R., Talbot, F.B., Weglarz, J., 1990. Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems. Eur. J. Oper. Res., 49(1):68-97.

[28]Pinder, J.P., Marucheck, A.S., 1996. Using discounted cash flow heuristics to improve project net present value. J. Oper. Manag., 14(3):229-240.

[29]Russell, A.H., 1970. Cash flows in networks. Manag. Sci., 16(5):357-373.

[30]Salewski, F., Schirmer, A., Drexl, A., 1997. Project scheduling under resource and mode identity constraints: model, complexity, methods, and application. Eur. J. Oper. Res., 102(1):88-110.

[31]Shtub, A., Etgar, R., 1997. A branch and bound algorithm for scheduling projects to maximize net present value: the case of time dependent, contingent cash flows. Int. J. Prod. Res., 35(12):3367-3378.

[32]Tormos, P., Lova, A., 2001. A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res., 102(1/4):65-81.

[33]Tsai, H.K., Yang, J.M., Kao, C.Y., 2002. Solving Traveling Salesman Problems by Combining Global and Local Search Mechanisms. Proc. Congress of Evolutionary Computation, p.1290-1295.

[34]Valls, V., Ballestin, F., Quintanilla, S., 2004. A population-based approach to the resource constrained project scheduling problem. Ann. Oper. Res., 131(1-4):305-324.

[35]Valls, V., Ballestin, F., Quintanilla, S., 2005. Justification and RCPSP: a technique that pays. Eur. J. Oper. Res., 165(2):375-386.

[36]Vanhoucke, M., 2006. A scatter Search Procedure for Maximizing the net Present Value of a Project under Renewable Resource Constraints. Vlerick Leuven Gent Working Paper Series 2006/40.

[37]Yin, A., 2004. A New Neighborhood Structure for the Job Shop Scheduling Problem. Proc. 3rd Int. Conf. on Machine Learning and Cybernetics, 4:2098-2101.

[38]Zhu, D., Padman, R., 1999. A metaheuristic scheduling procedure for resource-constrained projects with cash flows. Nav. Res. Log., 46(8):912-927.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE