Skip to main content
SpringerLink
Log in

An ant-based coordination mechanism for resource-constrained project scheduling with multiple agents and cash flow objectives

  • Published:
Flexible Services and Manufacturing Journal Aims and scope Submit manuscript

Abstract

We consider a multi-agent extension of the non-preemptive single-mode resource-constrained project scheduling problem with discounted cash flow objectives. Such a problem setting is related to project scheduling problems which involve different autonomous firms where project activities are uniquely assigned to the project parties (agents). Taking into account opportunistic agents and the resulting information asymmetry we propose a general decentralized negotiation approach which uses ideas from ant colony optimization. In the course of the negotiation the agents iteratively vote on proposed project schedules without disclosing preference information regarding cash flow values. Computational experiments serve to analyze the agent-based coordination mechanism in comparison to other approaches from the literature. The proposed mechanism turns out as an effective method for coordinating self-interested agents with conflicting goals which collaborate in resource-constrained projects.

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
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. While this objective function is used in some papers that consider the RCPSP-DC (e.g., Kimms 2001), some other papers use a slightly different function which models continuous discounting (e.g., Vanhoucke 2010): \( F\left( S \right) = \mathop \sum \limits_{j = 0}^{N - 1} c_{j} e^{{ - (1 + z)(s_{j} + d_{j} )}} \).

References

  • Abbasi GY, Arabiat YA (2001) A heuristic to maximize the net present value for resource-constrained project scheduling problems. Project Manag J 32:17–24

    Google Scholar 

  • Błażewicz J, Lenstra JK, Rinnooy Kan AHG (1983) Scheduling subject to resource constraints: classification and complexity. Discret Appl Math 5:11–24

    Article  MATH  Google Scholar 

  • Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999) Resource-constrained project scheduling: notation, classification, models, and methods. Eur J Oper Res 112:3–41

    Article  MATH  Google Scholar 

  • Bullnheimer B, Hartl RF, Strauss C (1999) A new rank based version of the ant system—a computational study. Cent Eur J Oper Res Econ 7:25–38

    MathSciNet  MATH  Google Scholar 

  • Chen W, Zhang J, Chung HS, Huang R, Liu O (2010) Optimizing discounted cash flows in project scheduling – an ant colony optimization approach. IEEE Trans Syst Man Cybern Part C (Appl Rev) 40:64–77

    Article  Google Scholar 

  • Colorni AM, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. In: Varela FJ, Bourgine P (eds) Proceedings of the first European conference on artificial life. Elsevier, New York, pp 134–142

    Google Scholar 

  • Debels D, Vanhoucke M (2007) A decomposition-based genetic algorithm for the resource-constrained project scheduling problem. Oper Res 55:457–469

    Article  MATH  Google Scholar 

  • Deng L, Lin Y, Chen M (2010) Hybrid ant colony optimization for the resource-constrained project scheduling problem. J Syst Eng Electron 21:71–76

    Google Scholar 

  • Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the travelling salesman problems. IEEE Trans Evol Comput 1:53–66

    Article  Google Scholar 

  • Ehtamo H, Verkama M, Hämäläinen RP (1999) How to select fair improving directions in a negotiation model over continuous issues. IEEE Trans Syst Man Cybern Part C (Appl Rev) 29:26–33

    Article  Google Scholar 

  • Ehtamo H, Kettunen E, Hämäläinen RP (2001) Searching for joint gains in multi-party negotiations. Eur J Oper Res 130:54–69

    Article  MATH  Google Scholar 

  • Fink A (2004) Supply chain coordination by means of automated negotiations. In: Proceedings of the 37th Hawaii international conference on system sciences, IEEE, 10 p, doi:10.1109/HICSS.2004.1265206

  • Fink A (2006) Supply chain coordination by means of automated negotiation between autonomous agents. In: Chaib-draa B, Müller J (eds) Multiagent based supply chain management, studies in computational intelligence, vol 28. Springer, Berlin, pp 351–372

    Chapter  Google Scholar 

  • Fink A (2007) Barwertorientierte Projektplanung mit mehreren Akteuren mittels eines verhandlungs-basierten Koordinationsmechanismus. In: Oberweis A, Weinhardt C, Gimpel H, Koschmider A, Pankratius V, Schnizler B (eds) eOrganisation: Service-, Prozess-, Market-Engineering, vol 2, Universitätsverlag Karlsruhe, pp 465–482

  • Hartmann S (1998) A competitive genetic algorithm for the resource-constrained project scheduling. Nav Res Logist 45:733–750

    Article  MathSciNet  MATH  Google Scholar 

  • Hartmann S, Briskorn D (2010) A survey of variants and extensions of the resource-constrained project scheduling problem. Eur J Oper Res 207:1–14

    Article  MathSciNet  MATH  Google Scholar 

  • He Z, Xu Y (2008) Multi-mode project payment scheduling problems with bonus-penalty structure. Eur J Oper Res 189:1191–1207

    Article  MATH  Google Scholar 

  • Herroelen WS, Dommelen PV, Demeulemeester EL (1997) Project network models with discounted cash flows—a guided tour through recent developments. Eur J Oper Res 100:97–121

    Article  MATH  Google Scholar 

  • Herroelen W, De Reyck B, Demeulemeester E (1998) Resource-constrained project scheduling: a survey of recent developments. Comput Oper Res 25:279–302

    Article  MathSciNet  MATH  Google Scholar 

  • Homberger J (2010) Decentralized multi-level uncapacitated lot-sizing by automated negotiation. 4OR: Q J Oper Res 8:155–180

    Article  MathSciNet  MATH  Google Scholar 

  • Homberger J (2011) A generic coordination mechanism for lot-sizing in supply chains. Electron Commerc Res 11:123–149

    Article  Google Scholar 

  • Homberger J (2012) A (μ, λ)-coordination mechanism for agent-based multi-project scheduling. OR Spectr 34:107–132

    Article  MathSciNet  MATH  Google Scholar 

  • Homberger J, Gehring H (2010) A pheromone-based negotiation mechanism for lot-sizing in supply chains. In: Proceedings of the 43rd Hawaii international conference on system sciences, IEEE, 10 p, doi:10.1109/HICSS.2010.26

  • Ito T, Hattori H, Klein M (2007) Multi-issue negotiation protocol for agents: Exploring nonlinear utility spaces. In: Proceedings of the twentieth international joint conference on artificial intelligence, pp 1347–1352. Hyderabad, India

  • Johnson DS, Aragon CR, McGeoch LA, Schevon C (1989) Optimization by simulated annealing: an experimental evaluation; part 1, graph partitioning. Oper Res 37:865–892

    Article  MATH  Google Scholar 

  • Jones GT (2006) Hybrid computational models for the mediated negotiation of complex contracts. In: Proceeding of 14th annual conference of the North American association for computational social and organizational science, Notre Dame, IN

  • Kimms A (2001) Maximizing the net present value of a project under resource constraints using a Lagrangian relaxation based heuristic with tight upper bounds. Ann Oper Res 102:221–236

    Article  MathSciNet  MATH  Google Scholar 

  • Klein M, Faratin P, Sayama H, Bar-Yam Y (2003a) Negotiating complex contracts. Group Decis Negot 12:111–125

    Article  Google Scholar 

  • Klein M, Faratin P, Sayama H, Bar-Yam Y (2003b) Protocols for negotiating complex contracts. IEEE Intell Syst 18:32–38

    Article  Google Scholar 

  • Kolisch R (1996) Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur J Oper Res 90:320–333

    Article  MATH  Google Scholar 

  • Kolisch R, Hartmann S (2006) Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur J Oper Res 174:23–37

    Article  MATH  Google Scholar 

  • Kolisch R, Padman R (2001) An integrated survey of deterministic project scheduling. Omega 29:249–272

    Article  Google Scholar 

  • Kolisch R, Sprecher A (1996) PSPLIB—a project scheduling library. Eur J Oper Res 96:205–216

    Article  Google Scholar 

  • Lai G, Sycara K (2009) A generic framework for automated multi-attribute negotiation. Group Decis Negot 18:169–187

    Article  Google Scholar 

  • Merkle D, Middendorf M, Schmeck H (2000) Pheromone evaluation in ant colony optimization. In: IECON 2000. 26th annual conference of the IEEE Industrial Electronics Society, vol 4, pp 2726–2731

  • Mika M, Waligora 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. Eur J Oper Res 164:639–668

    Article  MathSciNet  MATH  Google Scholar 

  • Nisan N, Roughgarden T, Tardos E, Vazirani VV (eds) (2007) Algorithmic game theory. Cambridge University Press, New York

    MATH  Google Scholar 

  • Özdamar L, Ulusoy G (1995) A survey on the resource-constrained project scheduling problem. IIE Trans 27:574–586

    Article  Google Scholar 

  • Rubinstein A (1982) Perfect equilibrium in a bargaining model. Econometrica 50:97–109

    Article  MathSciNet  MATH  Google Scholar 

  • Russell AH (1970) Cash flows in networks. Manag Sci 16:357–373

    Article  MATH  Google Scholar 

  • Russell RA (1986) A comparison of heuristics for scheduling projects with cash flows and resource restrictions. Manag Sci 32:1291–1300

    Article  Google Scholar 

  • Shou Y–Y (2006) Ant colony algorithm for scheduling resource constrained projects with discounted cash flows. Proceedings of the fifth IEEE international conference on machine learning and cybernetics, Dalian, pp 176–180

    Google Scholar 

  • Stadtler H (2009) A framework for collaborative planning and state-of-the-art. OR Spectr 31:5–30

    Article  MathSciNet  MATH  Google Scholar 

  • Stützle T, Hoos H (2000) MAX-MIN ant system. Futur Gener Comput Syst 16:889–914

    Article  Google Scholar 

  • Tung HW, Lin RJ (2005) Automated contract negotiation using a mediation service. In: Proceedings of the 7th IEEE international conference on E-commerce technology. Munich, Germany, pp 374–377

  • Ulusoy G, Özdamar L (1995) A heuristic scheduling algorithm for improving the duration and net present value of a project. Int J Oper Prod Manag 15:89–98

    Article  Google Scholar 

  • Vanhoucke M (2010) A scatter search heuristic for maximizing the net present value of a resource-constrained project with fixed activity cash flows. Int J Prod Res 48:1983–2001

    Article  MATH  Google Scholar 

  • Vanhoucke M, Demeulemeester E, Herroelen W (2001) On maximizing the net present value of a project under renewable resource constraints. Manag Sci 47:1113–1121

    Article  MATH  Google Scholar 

Download references

Acknowledgments

The authors are most grateful for the helpful comments of the anonymous reviewers which have contributed to improve the paper.

Author information

Authors and Affiliations

  1. Helmut-Schmidt-University Hamburg, Holstenhofweg 85, 22043, Hamburg, Germany

    Andreas Fink

  2. Stuttgart University of Applied Sciences, Schellingstr. 24, 70174, Stuttgart, Germany

    Jörg Homberger

Authors
  1. Andreas Fink
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jörg Homberger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Fink.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fink, A., Homberger, J. An ant-based coordination mechanism for resource-constrained project scheduling with multiple agents and cash flow objectives. Flex Serv Manuf J 25, 94–121 (2013). https://doi.org/10.1007/s10696-012-9136-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10696-012-9136-5

Keywords

Search

Navigation