Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling

F Lang, A Fink, Tobias Brandt

Research output: Contribution to journalArticleAcademicpeer-review

24 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)192-203
Number of pages12
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 2016

Research programs



Dive into the research topics of 'Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling'. Together they form a unique fingerprint.

Cite this