|
Vol: 57(71) No: 1 / March 2012 Issues About Application of Longest Path Algorithm for Project Duration Assessment Dalibor Dobrilovic Department of Information technology, University of Novi Sad, Technical Faculty ”Mihajlo Pupin”, Djure Djakovica bb, 23000 Zrenjanin, Serbia, phone: (+381) 550 515, e-mail: ddobrilo@tfzr.rs Vesna Jevtic Department of Information technology, University of Novi Sad, Technical Faculty ”Mihajlo Pupin”, Djure Djakovica bb, 23000 Zrenjanin, Serbia, e-mail: vesna@tfzr.uns.ac.rs Jelena Stojanov Department of Information technology, University of Novi Sad, Technical Faculty ”Mihajlo Pupin” , Djure Djakovica bb, 23000 Zrenjanin, Serbia, e-mail: jelena@tfzr.uns.ac.rs Keywords: shortest path algorithm, longest path algorithm, project duration assessment, project management Abstract Considering that project completion time has important role in the field of project management, it is obvious that the methods for its assessment are very important. Beside standard methods for project duration assessment (such as network planning methods: CPM, PERT, PDM), there are number of newly developed ones. Project management demands that new methods, beside their accuracy, can be easily implemented in any kind of project management software. Furthermore, there has to be possibility of their expanding in order to make assessments that take into account numerous unplanned influences on the project duration, i.e. worst case scenario. This paper presents one approach in modifying Dijsktra shortest path algorithm for project duration assessment. Graph diagram of one of the real life project plans is used for modified algorithm testing. Its original presentation, from one of the project management software, is converted in a graph diagram that is necessary for algorithm testing. This paper contains description of: conversion process, format of used data, the algorithm modification and results of algorithm testing. Algorithm modification includes two sub algorithms. One sub algorithm calculates longest path in the graph and it is used for calculation of project duration. The second sub algorithm is used for determining vertices on the longest path. The algorithm is implemented in the Matlab, in the first phase of this research, for testing purposes only. References [1] N. Dawood, “Estimating project and activity duration: a risk management approach using network analysis,” Construction Management and Economics, vol. 16, pp. 41–48, 1998. [2] D. Pons, “Does reduced uncertainty mean greater certainty? – Project management with uncertain durations,” in Proceedings of 2006 Conference on Project Management Institute of New Zealand (PMINZ), Christchurch, New Zealand, 2006. [3] K. A. Kirytopoulos, V. N. Leopoulos, and V. K. Diamantas, “PERT vs. Monte Carlo Simulation along with the suitable distribution effect,” Int. J. Project Organization and Management, vol. 1, no. 1, 2008. [4] M. Nagai, K. Kurihara, and N. Nishiuchi, “Project duration planning method based on the combination use of genetic algorithm and Monte Carlo simulation,” in Proceedings of 2002 IEEE International Conference on Systems, Man and Cybernetics, vol. 5, 2002. [5] G. Malkin, RFC 2453, RIP version 2, The Internet Society, November 1998. [6] R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958. [7] J. Moy, RFC 2328, OSPF version 2, The Internet Society, Apr. 1998. [8] R. Coltun, D. Ferguson, J. Moy, and A. Lindem, RFC 5340, The Internet Society, Jul. 2008. [9] D. Oran, RFC 1142, The Internet Society, Feb. 1990. [10] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959. [11] J. A. Anderson, Discrete Mathematics with Combinatorics Pearson, USA, 2004. [12] M. Hentschel, D. Lecking, and B. Wagner, “Deterministic path planning and navigation for an autonomous fork lift truck,” in Proceedings of 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV), Toulouse, France, 2007. [13] K.T. Vivaldini, J. P. M. Galdames, T. B. Pasqual, R. C. Araújo, R. M. Sobral, M. Becker, and G. A. P. Caurin, “Robotic forklifts for intelligent warehouses: Routing, path planning, and autolocalization,” in Proceedings of IEEE International Conference on Industrial Technology, Viña del Mar – Valparaíso, Chile, 2010. [14] K. T. Vivaldini, J. P. M. Galdames, T. B. Pasqual, M. Becker, and G. A. P. Caurin, “Intelligent Warehouses: focus on the automatic routing and path planning of robotic forklifts able to work autonomously,” Mechatronics Systems: Intelligent Transportation Vehicles, 2010. [15] I. Millington, Artificial Intelligence for Games. Morgan Kaufmann Publishers, 2006 by Elsevier Inc., 2006. [16] D. Dobrilovic, V. Jevtic, and J. Stojanov, “Application of modified shortest path algorithm for project duration assessment,” in Proceedings of 6th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI 2011), Timisoara, Romania, 2011, pp. 495–498. [17] S. Lim, H. Balakrishnan, D. Gifford, S. Madden, and D. Rus, “Stochastic motion planning and applications to traffic,” International Journal of Robotics Research archive, vol. 30, no. 6, DOI:10.1177/0278364910386259, May 2011. [18] I. Chabini, “Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time,” Transportation Research Record, vol. 1645, pp. 170–175, 1998. |