Genetic Algorithm for Selecting and Scheduling Interdependent Projects
Publication: Journal of Waterway, Port, Coastal, and Ocean Engineering
Volume 127, Issue 1
Abstract
Investment planning for systems with interdependent queues, such as a series of interacting waterway locks, is a very challenging problem. Under budget constraints, it must be determined which projects should be selected and when they should be funded to minimize the present value of total cost over the planning horizon. Due to interdependence among service stations (e.g., locks), investment planning for such systems cannot be analyzed separately for each station. Published models on investment planning for interdependent projects are rare and difficult to apply to a series of queuing systems. A genetic algorithm approach is presented in this paper for solving project sequencing and scheduling problems for such systems. A numerical example is designed to investigate the proposed algorithm. Results indicate that the proposed approach is quite efficient in finding very good solutions.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Clark, J. J., Hindelang, T. J., and Pritchard, R. E. ( 1984). Capital budgeting: Planning and control of capital expenditures, 2nd Ed., Prentice-Hall, Englewood Cliffs, N.J.
2.
Cochran, M. A., et al. ( 1971). “Investment model for R and D project evaluation and selection.” IEEE Trans. on Engrg. Mgmt., EM-18.
3.
Dai, M. D. M., and Schonfeld, P. ( 1998). “Metamodels for estimating waterway delays through series of queues.” Transp. Res. Part B, 32(1), 1–19.
4.
Erlenkotter, D. ( 1973). “Sequencing expansion projects.” Operations Res., 21, 542–553.
5.
Gen, M., and Cheng, R. ( 1997). Genetic algorithms and engineering design, Wiley, New York.
6.
Goldberg, D. E. ( 1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Reading, Mass.
7.
Johnson, E. L., Kostreva, M. M., and Suhl, U. H. ( 1985). “Solving 0-1 integer programming problems arising from large scale planning models.” Operations Res., 34(4), 803–819.
8.
Law, A. M., and Kelton, W. D. ( 1991). Simulation modeling & analysis, 2nd Ed., McGraw-Hill, New York.
9.
Martinelli, D. R. ( 1993). Investment planning of interdependent waterway improvement projects, Institute for Water Resource, U.S. Army Corps of Engineers, Belvoir, Va.
10.
Michalewicz, Z. ( 1996). Genetic algorithms + data structures = evolution programs, 3rd Ed., Springer, New York.
11.
Morin, T. L. (1974). “Optimality of a heuristic sequencing technique.”J. Hydr. Div., ASCE, 100(8), 1195–1202.
12.
Morin, T. L., and Esogbue, A. M. ( 1971). “Some efficient dynamic programming algorithms for the optimal sequencing and scheduling of water supply projects.” Water Resour. Res., 7(3), 479–484.
13.
Nemhauser, G. L., and Ullman, Z. ( 1969). “Discrete dynamic programming and capital allocation.” Mgmt. Sci., 15(9), 494–505.
14.
Papadimitrious, C. H., and Steiglitz, K. ( 1982). Combinatorial optimization: Algorithms and complexity, Prentice-Hall, Englewood Cliffs, N.J.
15.
Ting, C. J., and Schonfeld, P. ( 1998). “Optimization through simulation of waterway transportation investments.” Transp. Res. Rec. 1620, Transportation Research Board, Washington, D.C., 11–16.
16.
Wei, C. H., and Schonfeld, P. ( 1993). “An artificial neural network approach for evaluating transportation network improvements.” J. Advanced Transp., 27(2), 129–152.
17.
Wei, C. H., and Schonfeld, P. ( 1994). “Multiperiod network improvement model.” Transp. Res. Rec. 1443, Transportation Research Board, Washington, D.C., 110–118.
18.
Weingartner, H. M. ( 1966). “Capital budgeting of interrelated projects: Survey and synthesis.” Mgmt. Sci., 12(7), 485–516.
19.
Winston, W. L. ( 1987). Operations research: Application and algorithms, PWS Publishers, Boston.
Information & Authors
Information
Published In
History
Received: Apr 27, 1999
Published online: Feb 1, 2001
Published in print: Feb 2001
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.