A new heuristic solution method in resource-constrained project scheduling
1991; Wiley; Volume: 38; Issue: 3 Linguagem: Inglês
10.1002/1520-6750(199106)38
ISSN1520-6750
Autores Tópico(s)BIM and Construction Integration
ResumoNaval Research Logistics (NRL)Volume 38, Issue 3 p. 315-331 Article A new heuristic solution method in resource-constrained project scheduling Colin E. Bell, Colin E. Bell Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242Search for more papers by this authorJaemin Han, Jaemin Han Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242Search for more papers by this author Colin E. Bell, Colin E. Bell Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242Search for more papers by this authorJaemin Han, Jaemin Han Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242Search for more papers by this author First published: June 1991 https://doi.org/10.1002/1520-6750(199106)38:3 3.0.CO;2-7Citations: 55AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract A new heuristic method is presented for the resolution of multiresource constrained conflicts in project scheduling. In attempting to find a minimal makespan solution, the algorithm employs a simple procedure to generate a feasible solution with no backtracking. A postanalysis phase then applies a hill-climbing search. The solution method is different from existing heuristic methods in that it repairs resource conflicts rather than constructs detailed schedules by dispatching activities. Resource-violating sets of activities are identified which must be prevented from concurrent execution because this would violate resource constraints. Repairs are made by imposing an arc to sequence two activities in such a resource violating set. Computational results are compared with those of existing heuristics for the minimal makespan problem. References 1 Baker, K. R., Introduction to Sequencing and Scheduling, Wiley, New York, 1974. 2 Bell, C. E. and Park, K., "Solving Resource-Constrained Project Scheduling Problems by A* Search," Naval Research Logistics, 37, 61– 84 (1990). 3 Brand, J. D., Meyer, W. L., and Shaffer, L. R., " The Resource Scheduling Problem in Construction," Civil Engineering Studies Report No. 5, Department of Civil Engineering, University of Illinois, Urbana, IL, 1964. 4 Computer Associates International, Inc., SuperProject Expert, San Jose, CA, 1988. 5 Conway, R. W., Maxwell, W. L., and Miller, L. W., Theory of Scheduling, Addison-Wesley, Reading, MA, 1967. 6 Davis, E. W. and Heidorn, G. E., "An Algorithm for Optimal Project Scheduling under Multiple Resource Constraints," Management Science, 17 (12), B803– B816 (1971). 7 Davis, E. W. and Patterson, J. H., "A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling," Management Science, 21 (8), 944– 955 (1975). 8 Fendley, L. G., "Toward the Development of a Complete Multiproject Scheduling System," Journal of Industrial Engineering, 19 (10), 505– 515 (1968). 9 Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. 10 Han, J., " A New Heuristic Algorithm for Resource-Constrained Project Scheduling," Ph.D. dissertation, Department of Management Sciences, University of Iowa, 1988. 11 Johnson, T. J. R., " An Algorithm for the Resource-Constrained Project Scheduling Problem," Ph.D. thesis, Massachusetts Institute of Technology, 1967. 12 Kelley, J. E., " The Critical Path Method: Resources Planning and Scheduling," in J. Muth and G. Thompson (Eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, NJ, 1963, Chap. 21. 13 Knight, R. M., " Resource Allocation and Multi-Project Scheduling in a Research and Development Environment," M.S. thesis, School of Management, MIT, 1966. 14 Mize, J. H., " A Heuristic Scheduling Model for Multi-Project Organizations," Ph.D. thesis, Purdue University, 1964. 15 Pascoe, T. L., " An Experimental Comparison of Heuristic Methods for Allocating Resources," Ph.D. thesis, Cambridge University, 1965. 16 Patterson, J. H., "Alternative Methods of Project Scheduling with Limited Resources," Naval Research Logistics Quarterly, 20 (4), 767– 784 (1973). 17 Patterson, J. H., "Project Scheduling: The Effects of Problem Structure on Heuristic Performance," Naval Research Logistics Quarterly, 23 (1), 95– 123 (1976). 18 Patterson, J. H. and Roth, G., "Scheduling a Project under Multiple Resource Constraints: A Zero-One Programming Approach," AIIE Transactions, 8 (3), 449– 456, 1976. 19 Patterson, J. H., "A Comparison of Exact Approaches for Solving the Multiple Constrained, Project Scheduling," Management Science, 30 (7), 854– 867 (1984). 20 Stinson, J. P., Davis, E. W., and Khumawala, B. M., "Multiple Resource-Constrained Scheduling Using Branch and Bound," AIIE Transactions, 10 (3), 252– 259 (1978). 21 Talbot, F. B. and Patterson, J. H., "An Efficient Integer Programming Algorithm With Network Cuts for Solving Resource-Constrained Scheduling Problems," Management Science, 24 (11), 1163– 1174 (1978). 22 Wiest, J. D., "A Heuristic Model for Scheduling Large Projects with Limited Resources," Management Science, 13 (6), B359– 378 (1967). Citing Literature Volume38, Issue3June 1991Pages 315-331 ReferencesRelatedInformation
Referência(s)