Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling

•We study decentralized scheduling with heterogeneous machines and competing job sets.•The jobs belong to self-interested stakeholders with private preference information.•We present a metaheuristic-inspired negotiation protocol with various building blocks.•The protocol achieves (near) Pareto efficient outcomes and low aggregate social cost.•The limitedly informed protocol performs similar to informed centralized approaches.

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.