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.E. (1957) Dynamic programming. Princeton, NJ: Princeton University Press

Borgwardt, K.H., Brzank, J. (1994) Average saving effects in enumerative methods for solving knapsack problems. Journal of Complexity, 10(1): 129

Corman, T.H., Leiserson, C.E., Rivest, R.L. (1990) Introduction to algorithms. Cambridge, MA, itd: Massachusetts Institute of Technology Press / MIT Press

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

Feo, T.A., Resende, M.G.C. (1995) Greedy randomized adaptive search procedures. Journal of Global Optimization, 6 109-133

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

Lawrence, S.R. (1985) A computational comparison of heuristic scheduling techniques. Carnegie-Mellon University, Technical Report

Osgood, N. (2004) Simulation and resource. Presentation

Patterson, J.H. (1984) A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem. Management Science, 30(7): 854

Petrić, J. (1983) Operations research. Beograd: Savremena administracija

Pitsoulis, L.S., Resende, M.G.C. (2001) Greedy randomized adaptive search procedures. January 18

Sedgewick, R. (1984) Algorithms. Massachusetts, itd: Addison-Wesley

Valls, V., Balletin, F., Quintanilla, S. (2001) A population-based approach to the resource constrained project scheduling problem. University of Valencia, Technical report 10-2001

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

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

Downloads

Published

2009-09-01

Issue

Vol. 19 No. 2 (2009)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

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