Abstract
In this paper, a metaheuristic solution algorithm for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with discounted cash flows (MRCPSPDC) is proposed. This problem consists of determining a schedule such that the project is completed, maximizing the project’s net present value (NPV) while complying with the delivery deadline. The adaptative bacterial foraging optimization (ABFO) algorithm is a variation of the original bacterial foraging optimization (BFO), which is a nature-inspired metaheuristic optimization algorithm. We implement a version of the chemotactic operator based on a double justification of the activities given the cash flow. This metaheuristic has been tested in the PSPLIB and MMLIB benchmark datasets available in the literature with promising results. Our ABFO algorithm shows excellent performance in all tested instances and provides suitable solutions for the MRCPSP maximizing the NPV.
Similar content being viewed by others
References
Aboutalebi R, Najafi A, Ghorashi B (2012) Solving multi-mode resource-constrained project scheduling problem using two multi objective evolutionary algorithms. African Journal of Business Management 6(11):4057
Amador-Fontalvo JE, Paternina-Arboleda CD, Montoya-Torres JR (2014) Solving the heterogeneous vehicle routing problem with time windows and multiple products via a bacterial meta-heuristic. International Journal of Advanced Operations Management 6(1):81–100
Barrios A, Ballestin F, Valls V (2011) A double genetic algorithm for the mrcpsp/max. Computers & Operations Research 38(1):33–43
Bedworth DD, Bailey JE (1999) Integrated production control systems: management, analysis, and design. Wiley
Benjamini Y, Hochberg Y (1995) Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal statistical society: series B (Methodological) 57(1):289–300
Boctor FF (1996) A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes. European Journal of Operational Research 90(2):349–361
Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research 149(2):268–281
Chen AHL, Chyu C (2008) A memetic algorithm for maximizing net present value in resource-constrained project scheduling problem. In: 2008 IEEE congress on evolutionary computation (IEEE World Congress on Computational Intelligence), pp 2396–2403. https://doi.org/10.1109/CEC.2008.4631118
Chen H, Zhu Y, Hu K (2011) Adaptive bacterial foraging optimization. Abstract and Applied Analysis, 2011
Chen W-N, Zhang J, Chung HS-H, Huang R-Z, Liu O (2010) Optimizing discounted cash flows in project scheduling - an ant colony optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 40(1):64–77
Dayanand N, Padman R (2001) A two stage search heuristic for scheduling payments in projects. Annals of Operations Research 102(1):197–220
Debels D, De Reyck B, Leus R, Vanhoucke M (2006) A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research 169(2):638–653
Delgoshaei A, Ariffin MK, Baharudin B, Leman Z (2014) A backward approach for maximizing net present value of multi-mode pre-emptive resource-constrained project scheduling problem with discounted cash flows using simulated annealing algorithm. International Journal of Industrial Engineering and Management 5(3):151–158
Ge H, Tan G (2012) A cooperative intelligent approach for job-shop scheduling based on bacterial foraging strategy and particle swarm optimization. In: Computational Intelligence Systems in Industrial Engineering, pp 363–383. Springer
Hartmann S (2001) Project scheduling with multiple modes: a genetic algorithm. Annals of Operations Research 102(1–4):111–135
Hartmann S, Kolisch R (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research 127(2):394–407
Herroelen W, Demeulemeester E, De Reyck B (1999) A classification scheme for project scheduling. In: Project Scheduling, pp 1–26. Springer
Herroelen WS, Van Dommelen P, Demeulemeester EL (1997) Project network models with discounted cash flows a guided tour through recent developments. European Journal of Operational Research 100(1):97–121
Icmeli O, Erenguc SS (1994) A tabu search procedure for the resource constrained project scheduling problem with discounted cash flows. Computers & operations research 21(8):841–853
Jozefowska J, Mika M, Rozycki R, Waligóra G, Weglarz J (2001) Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research 102(1–4):137–155
Kar AK (2016) Bio inspired computing-a review of algorithms and scope of applications. Expert Systems with Applications 59:20–32
Kelly J (1963) The critical path method: Resource planning and scheduling. In: Muth J, Thompson G (eds) Industrial Scheduling. Prentice Hall, New Jersey, pp 347–365
Kolisch R (1995) Project Scheduling under Resource Constraints-Efficient Heuristics for Several Problem Classes. Physica-Verlag
Kolisch R, Drexl A (1997) Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions 29(11):987–999
Kolisch R, Hartmann S (1999) Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. Project Scheduling, International Series in Operations Research & Management Science. Springer, US, vol 14, pp 147–178
Kolisch R, Sprecher A (1996) Psplib-a project scheduling problem library. European Journal of Operational Research 96(1):205–216
Leyman P, Vanhoucke M (2015) A new scheduling technique for the resource-constrained project scheduling problem with discounted cash flows. International Journal of Production Research 53(9):2771–2786
Leyman P, Vanhoucke M (2016) Payment models and net present value optimization for resource-constrained project scheduling. Computers & Industrial Engineering 91:139–153
Lova A, Tormos P, Cervantes M, Barber F (2009) An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics 117(2):302–316
Majhi R, Panda G, Majhi B, Sahoo G (2009) Efficient prediction of stock market indices using adaptive bacterial foraging optimization (abfo) and bfo based techniques. Expert Systems with Applications 36(6):10097–10104
Mika M, Waligóra G, Weglarz J (2005) Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research 164(3):639–668
Montoya-Torres JR, Gómez-Vizcaíno LS, Solano-Charris EL, Paternina-Arboleda CD (2010) Global bacteria optimization meta-heuristic algorithm for jobshop scheduling. International Journal of Operations Research and Information Systems (IJORIS) 1(4):47–58
Panda R, Naik MK (2012) A crossover bacterial foraging optimization algorithm. Applied Computational Intelligence and Soft Computing 2012:23
Passino KM (2002) Biomimicry of bacterial foraging for distributed optimization and control. IEEE control systems 22(3):52–67
Saber AY, Venayagamoorthy GK (2008) Economic load dispatch using bacterial foraging technique with particle swarm optimization biased evolution. In: 2008 IEEE Swarm Intelligence Symposium, pp 1–8. IEEE
Solano-Charris EL, Gómez-Vizcaíno LS, Montoya-Torres JR, Paternina-Arboleda CD (2012) Global bacteria optimization meta-heuristic: performance analysis and application to shop scheduling problems. In: Hybrid Algorithms for Service, Computing and Manufacturing Systems: Routing and Scheduling Solutions, pp 178–194. IGI Global
Tantisuvanichkul V (2014) Optimising net present value using priority rule-based scheduling. PhD thesis, University of Manchester
Ulusoy G, Sivrikaya-Şerifoğlu F, Şahin Ş (2001) Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows. Annals of Operations Research 102(1–4):237–261
Vaisakh K, Praveena P, Rao SRM (2010) PSO-DV and bacterial foraging optimization based dynamic economic dispatch with non-smooth cost functions. In: 2009 International Conference on Advances in Computing, Control, and Telecommunication Technologies, vol 1, pp 131–139. IEEE
Valls V, Laguna M, Lino P, Pérez A, Quintanilla S (1999) Project scheduling with stochastic activity interruptions. In: Project Scheduling, pp 333–353. Springer
Van Peteghem V, Vanhoucke M (2010) A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research 201(2):409–418
Van Peteghem V, Vanhoucke M (2011) Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem. Journal of Heuristics 17(6):705–728
Van Peteghem V, Vanhoucke M (2014) An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research 235(1):62–72
Vanhoucke M, Demeulemeester E, Herroelen W (2001) On maximizing the net present value of a project under renewable resource constraints. Management Science 47(8):1113–1121
Wan M, Li L, Xiao J, Wang C, Yang Y (2012) Data clustering using bacterial foraging optimization. Journal of Intelligent Information Systems 38(2):321–341
Weglarz J, Józefowska J, Mika M, Waligóra G (2011) Project scheduling with finite or infinite number of activity processing modes: A survey. European Journal of Operational Research 208(3):177–205
Zang, T., He, Z., and Ye, D. (2010). Bacterial foraging optimization algorithm with particle swarm optimization strategy for distribution network reconfiguration. In: International Conference in Swarm Intelligence, pp 365–372. Springer
Zhengwei G, Pang H, Wang D (2011) Adaptive bacterial foraging optimization and its application for bus scheduling. Journal of System Simulation 23(6):1151–1160
Acknowledgements
LFM-D was supported by the Colombian Agency for Research and Development (COLCIENCIAS), contract FP44842-068-2018, and received a PhD scholarship from Universidad del Norte, Barranquilla, Colombia. LFM-D is a doctoral student at Universidad del Norte. Some of this work is to be presented to the PhD program in partial fulfillment of the requirements for the PhD degree. The sponsor of the study has no role in study design; in the collection, analysis, and interpretation of data; in the writing of the report; and in the decision to submit the article for publication.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Machado-Domínguez, L.F., Paternina-Arboleda, C.D., Vélez, J.I. et al. An adaptative bacterial foraging optimization algorithm for solving the MRCPSP with discounted cash flows. TOP 30, 221–248 (2022). https://doi.org/10.1007/s11750-021-00612-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-021-00612-2