IDEAS home Printed from
   My bibliography  Save this article

Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling


  • Lang, Fabian
  • Fink, Andreas
  • Brandt, Tobias


We consider a hard decentralized scheduling problem with heterogeneous machines and competing job sets that belong to different self-interested stakeholders (agents). The determination of a beneficial solution, i.e., a respective contract in terms of a common schedule, is particularly difficult due to information asymmetry and self-interested behavior of the involved agents. The agents intend to minimize their individual costs that consist of tardiness cost and their share of the machine operating cost. The aim of this study is to find socially beneficial outcomes by means of negotiation mechanisms that comply with decentralized information and conflicting interests. For this purpose, we present an automated negotiation protocol, which is inspired by metaheuristics, along with a set of optional building blocks. In the protocol, new solutions are iteratively generated, as mutations of a single provisional contract, and proposed to the agents, while feasible rules with quotas restrict the acceptance decisions of the agents. The computational experiments show that the protocol—without central information and subject to strategic behavior—can achieve high quality solutions which are very close to results from centralized multi-criteria procedures. Particular building block configurations yield improved outcomes. Concluding, the considered scheduling problem enhances standard scheduling models by incorporating multiple stakeholders, nonlinear cost functions, and machine operating cost, whereas the presented negotiation approach contributes to the methodology and practice of collaborative decision making.

Suggested Citation

  • Lang, Fabian & Fink, Andreas & Brandt, Tobias, 2016. "Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling," European Journal of Operational Research, Elsevier, vol. 248(1), pages 192-203.
  • Handle: RePEc:eee:ejores:v:248:y:2016:i:1:p:192-203
    DOI: 10.1016/j.ejor.2015.06.058

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Dudek, Gregor & Stadtler, Hartmut, 2005. "Negotiation-based collaborative planning between supply chains partners," European Journal of Operational Research, Elsevier, vol. 163(3), pages 668-687, June.
    2. Andrew Cook & Graham Tanner & Adrian Lawes, 2012. "The Hidden Cost of Airline Unpunctuality," Journal of Transport Economics and Policy, University of Bath, vol. 46(2), pages 157-173, May.
    3. Mor, Baruch & Mosheiov, Gur, 2010. "Scheduling problems with two competing agents to minimize minmax and minsum earliness measures," European Journal of Operational Research, Elsevier, vol. 206(3), pages 540-546, November.
    4. Zhang, Linlan & Song, Haigang & Chen, Xueguang & Hong, Liu, 2011. "A simultaneous multi-issue negotiation through autonomous agents," European Journal of Operational Research, Elsevier, vol. 210(1), pages 95-105, April.
    5. Geiger, Martin Josef, 2007. "On operators and search space topology in multi-objective flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 181(1), pages 195-206, August.
    6. Kersten, Gregory E. & Mallory, Geoffrey R., 1990. "Supporting problem representations in decisions with strategic interactions," European Journal of Operational Research, Elsevier, vol. 46(2), pages 200-215, May.
    7. John C. Harsanyi, 1955. "Cardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Utility," Journal of Political Economy, University of Chicago Press, vol. 63, pages 309-309.
    8. Myerson, Roger B, 1981. "Utilitarianism, Egalitarianism, and the Timing Effect in Social Choice Problems," Econometrica, Econometric Society, vol. 49(4), pages 883-897, June.
    9. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    10. Geiger, Martin Josef, 2010. "On heuristic search for the single machine total weighted tardiness problem - Some theoretical insights and their empirical verification," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1235-1243, December.
    11. Strbac, Goran, 2008. "Demand side management: Benefits and challenges," Energy Policy, Elsevier, vol. 36(12), pages 4419-4426, December.
    12. Cheng, T.C.E. & Ng, C.T. & Yuan, J.J., 2008. "Multi-agent scheduling on a single machine with max-form criteria," European Journal of Operational Research, Elsevier, vol. 188(2), pages 603-609, July.
    13. Bodenstein, Christian & Schryen, Guido & Neumann, Dirk, 2012. "Energy-aware workload management models for operation cost reduction in data centers," European Journal of Operational Research, Elsevier, vol. 222(1), pages 157-167.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Homberger, Jörg & Fink, Andreas, 2017. "Generic negotiation mechanisms with side payments – Design, analysis and application for decentralized resource-constrained multi-project scheduling problems," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1001-1012.
    2. Kuen-Fang Jea & Jen-Ya Wang & Chih-Wei Hsu, 2019. "Two-Agent Advertisement Scheduling on Physical Books to Maximize the Total Profit," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(03), pages 1-24, June.
    3. Gärttner, Johannes & Flath, Christoph M. & Weinhardt, Christof, 2018. "Portfolio and contract design for demand response resources," European Journal of Operational Research, Elsevier, vol. 266(1), pages 340-353.


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:248:y:2016:i:1:p:192-203. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Haili He). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.