Skip to main content
SpringerLink
Log in

An adaptative bacterial foraging optimization algorithm for solving the MRCPSP with discounted cash flows

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Barrios A, Ballestin F, Valls V (2011) A double genetic algorithm for the mrcpsp/max. Computers & Operations Research 38(1):33–43

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Dayanand N, Padman R (2001) A two stage search heuristic for scheduling payments in projects. Annals of Operations Research 102(1):197–220

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Kar AK (2016) Bio inspired computing-a review of algorithms and scope of applications. Expert Systems with Applications 59:20–32

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Leyman P, Vanhoucke M (2016) Payment models and net present value optimization for resource-constrained project scheduling. Computers & Industrial Engineering 91:139–153

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Panda R, Naik MK (2012) A crossover bacterial foraging optimization algorithm. Applied Computational Intelligence and Soft Computing 2012:23

    Article  Google Scholar 

  • Passino KM (2002) Biomimicry of bacterial foraging for distributed optimization and control. IEEE control systems 22(3):52–67

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

Download references

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

  1. Department of Industrial Engineering, Universidad del Norte, Barranquilla, Colombia

    Luis F. Machado-Domínguez, Carlos D. Paternina-Arboleda & Jorge I. Vélez

  2. Department of Mathematics and Statistics, Universidad del Norte, Barranquilla, Colombia

    Agustín Barrios-Sarmiento

Authors
  1. Luis F. Machado-Domínguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos D. Paternina-Arboleda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jorge I. Vélez
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Agustín Barrios-Sarmiento
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luis F. Machado-Domínguez.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-021-00612-2

Keywords

Mathematics Subject Classification

Search

Navigation