Similar articles

Abstract: 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.

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