Heuristic algorithm for single resource constrained project scheduling problem based on the dynamic programming

Authors

  • Ivan Stanimirović Department of Mathematics and informatics, Faculty of Sciences and Mathematics, Niš
  • Marko Petković Department of Mathematics and informatics, Faculty of Sciences and Mathematics, Niš
  • Predrag Stanimirović Department of Mathematics and informatics, Faculty of Sciences and Mathematics, Niš
  • Miroslav Ćirić Department of Mathematics and informatics, Faculty of Sciences and Mathematics, Niš

DOI:

https://doi.org/10.2298/YJOR0902281S

Keywords:

Abstract

We introduce a heuristic method for the single resource constrained project scheduling problem, based on the dynamic programming solution of the knapsack problem. This method schedules projects with one type of resources, in the non-preemptive case: once started an activity is not interrupted and runs to completion. We compare the implementation of this method with well-known heuristic scheduling method, called Minimum Slack First (known also as Gray-Kidd algorithm), as well as with Microsoft Project.

References

Bellman, R., Dynamic Programming, Princeton University Press, 1957.

Borgwardt, K.H., and Brzank, J., “Average saving effects in enumerative methods for solving knapsack problems”, Journal of Complexity, 10 (1994) 129–141.

Cormen, T. H., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, MIT Press & McGraw-Hill, 1990.

Osgood, N., Simulation and Resource-Based Scheduling, Presentation, 2004.

Petrić, J., Operations Research, Savremena Administracija, Beograd, 1983. (In Serbian)

Patterson, J.H., “A comparison of exact approaches for solving the multiple constrained resource project scheduling problem”, Management Science, 30 (7) (1984) 854-867.

Davies, E.M., “An experimental investigation of resource allocation in multiactivity projects”, Operational Research Quarterly, 24 (11) (1976) 1186-1194.

Feo, T., and Resende, M.G.C., “Greedy randomized adaptive search procedures”, Journal of Global Optimization, 6 (1995) 109–134.

Kochetov, Y., and Stolyar, A., “Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem”, in: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies, Russia, 2003.

Lawrence, S.R., “A computational comparison of heuristic scheduling techniques”, Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, 1985.

Pitsoulis, L.S., and Resende, M.G.C., “Greedy randomized adaptive search procedures”, AT&T Labs Research Technical Report, January 18, 2001.

Sedgewick, R., Algorithms, Addison-Wesley Publishing Company, Massachusetts, 1984.

Valls, V., Balletin, F., and Quintanilla, S., “A population-based approach to the resource constrained project scheduling problem”, Technical Report 10-2001, University of Valencia, 2001.

Valls, V., Balletin, F., and Quintanilla, S., “A population-based approach to the resource constrained project scheduling problem”, Annals of Operations Research, 131 (2004) 305-324.

Verma, S., “An optimal breadth-first algorithm for the preemptive resource-constrained project scheduling problem”, Second World Conference on POM and 15th Annual POM Conference, Cancun, Mexico, April 30 - May 3, 2004.

Downloads

Published

2009-09-01

Issue

Vol. 19 No. 2 (2009)

Section

Research Articles

License

Copyright (c) 2009 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.