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

Dirk Briskorn and Stefan Waldherr

European Journal of Operational Research, 2022, vol. 301, issue 3, 815-827

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.

Keywords: Scheduling; Distributed scheduling; Price of anarchy; Coordination mechanisms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172100998X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:301:y:2022:i:3:p:815-827

DOI: 10.1016/j.ejor.2021.11.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().