Chaotic vibrating particles system for resource-constrained project scheduling problem

Document Type : Article

Authors

1 Centre of Excellence for Fundamental Studies in Structural Engineering, Iran University of ‎Science and Technology, Narmak, Tehran, P.O. Box 16846-13114, Iran‎

2 Centre of Excellence for Fundamental Studies in Structural Engineering, Iran University of Science and Technology, Narmak, Tehran, P.O. Box 16846-13114, Iran.

Abstract

Project scheduling in the resource-constrained situation is one of the key issues of project-oriented organizations. The aim of resource-constrained project scheduling problem (RCPSP) is finding a schedule with minimum makespan by considering precedence and resource constraints. RCPSP is a combinatorial optimization problem and belongs to the class of NP-hard problems. The exact methods search the entire search space and are unable to solve large-sized project networks. Thus metaheuristics are used to solve this problem with less computational time. Due to the probabilistic nature of metaheuristics, it is a challenging problem to balance between exploitation and exploration phases. The literature review shows that embedding with chaos improves both the convergence speed and the local optima avoidance of metaheuristics. This paper presents a Chaotic Vibrating Particles System (CVPS) optimization algorithm for solving the RCPSP. Vibrating Particles System (VPS) is a physic inspired metaheuristic which mimics the free vibration of single degree of freedom systems with viscous damping. The performance and applicability of the CVPS is compared with the standard VPS, and five well known algorithms on three benchmark instances of the RCPSPs Experimental studies reveals that the proposed optimization method is a promising alternative to assist project managers in dealing with RCPSP.

Keywords

Main Subjects

References

References:
1. Sebt, M.H., Zarandi, M.H.F., and Alipouri, Y. "Genetic algorithms to solve resource-constrained project scheduling problems with variable activity durations", Int. J. Civ. Eng., 11, pp. 189-198 (2013).
2. Kolisch, R. and Sprecher, A. "PSPLIB - A project scheduling problem library", Eur. J. Oper. Res., 96, pp. 205-216 (1996).
3. Ballestin, F. "When it is worthwhile to work with the stochastic RCPSP?", J. Sched., 10, pp. 153-166 (2007).
4. Hartmann, S. and Drexl, A "Project scheduling with multiple modes: a comparison of exact algorithms", Networks, 32, pp. 283-297 (1998).
5. Harvey, R.T. and Patterson, J.H. "An implicit enumeration algorithm for the time-cost tradeoff problem in project network analysis", Found. Control. Eng., 4, pp. 107-117 (1979).
6. Hindelang, T. and Muth, J. "A dynamic programming algorithm for decision CPM networks", Oper. Res., 27, pp. 225-241 (1979).
7. Chen, W., Shi, Y., Teng, H., et al. "An efficient hybrid algorithm for resource-constrained project scheduling", Inf. Sci. (Ny), 180, pp. 1031-1039 (2010).
8. Giran, O., Temur, R., and Bekdas, G. "Resource constrained project scheduling by harmony search algorithm", KSCE J. Civ. Eng., 21, pp. 479-487 (2017).
9. Kaveh, A., Khanzadi, M., and Alipour, M. "Fuzzy resource constraint project scheduling problem using CBO and CSS algorithms", Int. J. Civ. Eng., 14(5), pp. 325-337 (2016).
10. Khanzadi, M., Kaveh, A., Alipour, M., and Aghmiuni, H.K. "Application of CBO and CSS for resource allocation and resource leveling problem", Iran. J. Sci. Technol. - Trans. Civ. Eng., 40, pp. 119-132 (2015).
11. Kaveh, A. and Vazirinia, Y. "Optimization of tower crane location and material quantity between supply and demand points: A comparative study", Period. Polytech. Civ. Eng., 62, pp. 732-745 (2018).
12. Kaveh, A., Hosseini Vaez, S.R., and Hosseini, P. "Enhanced vibrating particles system algorithm for damage identification of truss structures", Sci. Iran., Trans. A, Civ. Eng., 26(1), pp. 246-256 (2017).
13. Kaveh, A. and Zolghadr, A. "Comparison of nine metaheuristic algorithms for optimal design of truss structures with frequency constraints", Adv. Eng. Softw., 76, pp. 9-30 (2014).
14. Kaveh, A. and Ilchi Ghazaan, M. "A new metaheuristic algorithm: vibrating particles system", Sci. Iran., Trans. A, Civ. Eng., 24, pp. 1-32 (2017).
15. Golberg, D.E. "Genetic algorithms in search, optimization, and machine learning", Addison-Wesley Publishing Company, Reading, Massachusetts (1989).
16. Eberhart, R., and Kennedy, J. "A new optimizer using particle swarm theory", In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science., Nagoya, Japan, pp. 39-43 (1995).
17. Kaveh, A. and Farhoudi, N. "A new optimization method: Dolphin echolocation", Adv. Eng. Softw., 59, pp. 53-70 (2013).
18. Atashpaz-Gargari, E. and Lucas, C. "Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition", In: 2007 IEEE Congress on Evolutionary Computation, pp. 4661-4667 (2007).
19. Kaveh, A., Motie Share, M.A., and Moslehi, M. "Magnetic charged system search: a new meta-heuristic algorithm for optimization", Acta Mech., 224, pp. 85- 107 (2013).
20. Kaveh, A. and Mahdavi, V.R. "Colliding bodies optimization method for optimum discrete design of truss structures", Comput. Struct., 139, pp. 43-53 (2014).
21. Geem, Z.W., Kim, J.H., and Loganathan, G.V. "A new heuristic optimization algorithm: Harmony search", Simulation, 76(2), pp. 60-68 (2001).
22. Kaveh, A., Advances in Metaheuristic Algorithms for Optimal Design of Structures, 2nd Ed. Springer International Publishing, Cham, Switzerland (2017).
23. Mirjalili, S. and Gandomi, A.H. "Chaotic gravitational constants for the gravitational search algorithm", Appl. Soft Comput. J., 53, pp. 407-419 (2017).
24. Saremi, S., Mirjalili, S., and Lewis, A. "Biogeographybased optimisation with chaos", Neural Comput. Appl., 25, pp. 1077-1097 (2014).
25. Kaveh, A., Sheikholeslami, R., Talatahari, S., and Keshvari-Ilkhichi, M. "Chaotic swarming of particles: A new method for size optimization of truss structures", Adv. Eng. Softw., 67, pp. 136-147 (2014).
26. Gandomi, A.H. and Yang, X.S. "Chaotic bat algorithm" , J. Comput. Sci., 5, pp. 224-232 (2014).
27. Fiori, S. "An improved chaotic optimization algorithm applied to a DC electrical motor modeling", Entropy, 19, pp. 1-27 (2017).
28. Ditto, W. and Munakata, T. "Principles and applications of chaotic systems", Commun. ACM, 38, pp. 96-102 (1995).
29. Kaveh, A. and Talatahari, S. "A novel heuristic optimization method: charged system search", Acta Mech, 213, pp. 267-289 (2010).
30. Kaveh, A., Dadras Eslamlou, A., and Montazeran, H. "Chaotic enhanced colliding bodies algorithms for size optimization of truss structures", Acta Mech., 229(7), pp. 2883-2907 (2018).
31. Tavazoei, M.S. and Haeri, M. "An optimization algorithm based on chaotic behavior and fractal nature", J. Comput. Appl. Math., 206, pp. 1070-1081 (2007).
32. Shenker, S.J. "Scaling behavior in a map of a circle onto itself: Empirical results", Phys. D. Nonlinear Phenom., 5, pp. 405-411 (1982).
33. Hilborn, R.C., Chaos and Nonlinear Dynamics: an Introduction for Scientists and Engineers, 2nd Ed. Oxford Univ. Press, New York (2004).
34. He, D., He, C., Jiang, L.G., et al. "Chaotic characteristics of a one-dimensional iterative map with infinite collapses", IEEE Trans. Circuits. Syst. I Fundam. Theory Appl., 48, pp. 900-906 (2001).
35. May, R.M. "Simple mathematical models with very complicated dynamics", Nature, 261, pp. 459-467 (1976).
36. Devaney, R.L., An Introduction to Chaotic Dynamical Systems, Addison-Wesley (1987).
37. Peitgen, H., Jurgens, H., and Saupe, D., Chaos and Fractals, Springer-Verlag, Berlin, Germany (1992).
38. Tavazoei, M.S. and Haeri, M. "Comparison of different one-dimensional maps as chaotic search pattern in chaos optimization algorithms", Appl. Math. Comput., 187, pp. 1076-1085 (2007).
39. Anagnostopoulos, K. and Koulinas, G. "Resourceconstrained critical path scheduling by a GRASPbased hyperheuristic", J. Comput. Civ. Eng., 26, pp. 204-213 (2012).
40. Sears, S.K., Sears, G.A., and Clough, R.H., Construction Project Management, A Practical Guide to Field Construction, 5th Ed., John Wiley & Sons, Inc., Hoboken, New Jersey (2008).
41. Christodoulou, S. "Scheduling resource-constrained projects with ant colony optimization artificial agents", J. Comput. Civ. Eng., 24, pp. 45-55 (2010).
42. MATLAB Software (2017).
43. Kaveh, A. and Vazirinia, Y. "Construction site layout planning problem using metaheuristic algorithms: a comparative study", Iran. J. Sci. Technol. - Trans. Civ. Eng., 43(2), pp. 105-115 (2019).
44. Kaveh, A. and Ilchi Ghazaan, M. "Vibrating particles system algorithm for truss optimization with multiple natural frequency constraints", Acta Mech., 228, pp. 307-322 (2017).
45. Tran, D., Cheng, M., and Cao, M. "Solving  resourceconstrained project scheduling problems using hybrid artificial bee colony with differential evolution", J. Comput. Civ. Eng., 30, pp. 1-10 (2016).
Scientia Iranica
Volume 27, Issue 4
Transactions on Civil Engineering (A)
July and August 2020
Pages 1826-1842

Files

Share

How to cite

Statistics