Stability and fairness in the job scheduling problem

Eric Bahel () and Christian Trudeau

No 1803, Working Papers from University of Windsor, Department of Economics

Abstract: The job scheduling problem is a classic operational research problem in which agents have jobs to be executed by machines in given time slots, with each machine being able to process only one job at a time. We study this problem using cooperative game theory, focusing on how to divide the minimum cost (of executing all jobs) between the agents. First, we characterize the set of stable allocations, which all charge only users whose jobs are executed in peak-demand time periods. Second, using properties designed to avoid strategic mergers or splits of the jobs, we offer axiomatizations for two remarkable stable allocation rules. Third, observing that all stable rules fail Unanimity Lower Bound (ULB), a property requiring that everybody pay an equal share of the first machine (since it is needed by all), we study and axiomatize the Shapley value, which satisfies ULB. A compromise is then proposed between Stability and ULB.

Keywords: game theory; cost sharing; job scheduling; stability; unanimity lower bound; Shapley value. (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
Pages: 26 pages
Date: 2018-05
New Economics Papers: this item is included in nep-des and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://web2.uwindsor.ca/economics/RePEc/wis/pdf/1803.pdf First version, 2018 (application/pdf)

Related works:
Journal Article: Stability and fairness in the job scheduling problem (2019)
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:wis:wpaper:1803

Access Statistics for this paper

More papers in Working Papers from University of Windsor, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Christian Trudeau ().