Abstract
The Resource Constrained Project Scheduling Problem (RCPSP) is a prominent and a noteworthy NP-hard Combinatorial Optimization problem in the field of Operations Research and Management. It is a proven complex problem which involves constrained availability of resources, within which activities in a project should be optimally organized, keeping in mind the activity precedences, so that the project schedule is minimized. To efficiently solve the problem, many Evolutionary and Swarm Intelligence metaheuristics have been proposed, which have attempted to solve the problem optimally. This paper presents a novel Swarm Intelligence algorithm based on the Firefly Algorithm (FA). Applying the FA to solve the RCPSP problem, however, involved discretizing the FA as RCPSP is a discrete problem and FA by nature is continuous. The presented algorithm has been checked on standard benchmark test problems available in the literature and also compared with existing contemporary Swarm Intelligence and Evolutionary Algorithms available. The results of the experiments also justify the effectiveness of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Artigues, C.: The Resource-Constrained Project Scheduling Problem. http://www.iste.co.uk/data/doc_dtalmanhopmh.pdf
Sprecher, A., Kolisch, R.: PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. Eur. J. Oper. Res. 96(1), 205–216 (1997)
Merkle, D., Schmeck, H., Middendorf, M.: Ant colony ofor resource-constrained project scheduling. IEEE Trans. Evol. Comp. 6(4), (2002)
Brucker, P., Knust S., Schoo A., Thiele, O.: A branch and bound algorithm for the resource-constrained project scheduling problem, Eur. J. Oper. Res. 107, 272–288 (1998)
Blazewicz, J., Lenstra, J.K., Rinnooy, K.A.H.G.: Scheduling subject to resource constraints: classification and complexity. Discret. Appl. Math. 5(1), 11–24 (1983)
Hartmann, S., Kolisch, R.: Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur. J. Oper. Res. 127(2), 394–407 (2000)
Zhou, Y., Guo, Q., Gan, R.: Improved ACO algorithm for Resource-Constrained Project Scheduling Problem. In: International Conference on Artificial Intelligence and Computational Intelligence, AICI ‘09, IEEE, vol. 3, pp. 358–365 (2009)
Yang, X.S.: Nature-inspired Metaheuristic Algorithm. Luniver Press (2008)
Vanhoucke, M.: Project management with dynamic scheduling. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-40438-2
Kolisch, R., Hartmann, S.: Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur. J. Oper. Res. 174, 23–37 (2006)
Kolisch, R., Hartmann, S.: Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis. In: Weglarz, J. (ed.) Project Scheduling: Recent Models Algorithms and Applications, pp. 147–178. Kluwer Academic Publishers, Berlin (1999)
Kolisch, R., Padman, R.: An integrated survey of deterministic project scheduling. Omega 29, 249–272 (2001)
Koulinas, G., Kotsikas, L., Anagnostopoulos, K.: A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem. Inf. Sci. 277, 680–693 (2014)
Kumar, N., Vidyarthi, D.P.: A model for resource-constrained project scheduling using adaptive PSO. Soft. Comput. 20(4), 1565–1580 (2016)
Ziarati, K., Akbari, R., Zeighami, V.: On the performance of bee algorithms for resource-constrained project scheduling problem. Appl. Soft Comput. 11(4), 3720–3733 (2011)
Bibiks K., Hu F., Li J., Smith, A.: Discrete Cuckoo Search for Resource Constrained Project Scheduling Problem. In: International Conference on Computational Science and Engineering, IEEE, pp. 240–245 (2015)
Marichelvam, M.K., Prabahkaran, T., Yang, X.S.: A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems. IEEE Trans. Evol. Comput. 18(2), 301–305 (2014)
Karthikeyan, S., Asokan, P., Nickolas, S., Page, T.: A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int. J. Bio-Inspired Comput. 7(6), 386–401 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Roy, B., Sen, A.K. (2020). A Novel Metaheuristic Approach for Resource Constrained Project Scheduling Problem. In: Pant, M., Kumar Sharma, T., Arya, R., Sahana, B., Zolfagharinia, H. (eds) Soft Computing: Theories and Applications. Advances in Intelligent Systems and Computing, vol 1154. Springer, Singapore. https://doi.org/10.1007/978-981-15-4032-5_49
Download citation
DOI: https://doi.org/10.1007/978-981-15-4032-5_49
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-4031-8
Online ISBN: 978-981-15-4032-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)