Anarchy in the UJ: Coordination mechanisms for minimizing the number of late jobs

Dirk Briskorn*, Stefan Waldherr

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the distributed scheduling problem on parallel machines with the central objective of maximizing the number of on-time jobs. Jobs are self-interested utility-maximizers that can choose the machines they are processed on and are exclusively interested in reducing their own private objective function. Each machine processes the jobs according to a local policy. We discuss Nash equilibria in the resulting schedules and perform a thorough analysis of the resulting (absolute) prices of anarchy for various parallel machine environments, utilities of the agents, and local policies of the machines. We show that local policies that are based on simple sorting-based procedures like shortest processing time first (SPT) and earliest due date first (EDD) lead to big losses in welfare compared to the global optimum. However, when employing Moore-Hodgson's algorithm as a local policy, we can prove a price of anarchy of (2m−1)/m for identical machines and a price of anarchy of 2 for related and unrelated parallel machines. Moreover, we show how these results can be used to prove approximation ratios for greedy scheduling algorithms. This paper is the first to prove approximation ratios for two greedy scheduling procedures, turning them from simple heuristics into actual approximation ratios with a provable approximation ratio.

Original languageEnglish
JournalEuropean Journal of Operational Research
DOIs
Publication statusAccepted/In press - 2021

Bibliographical note

Funding Information:
The authors want to thank Bastian Diekkamp for fruitful discussions on early versions of the proofs. The first author has been supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 425058257.

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Coordination mechanisms
  • Distributed scheduling
  • Price of anarchy
  • Scheduling

Fingerprint

Dive into the research topics of 'Anarchy in the UJ: Coordination mechanisms for minimizing the number of late jobs'. Together they form a unique fingerprint.

Cite this