Stability and fairness in the job scheduling problem

Eric Bahel () and Christian Trudeau

Games and Economic Behavior, 2019, vol. 117, issue C, 1-14

Abstract: The job scheduling problem is a classic operations 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, we introduce a number of natural properties that allow to split the cost in a fair and consistent way. Using these desirable properties, we offer axiomatizations for two cost sharing methods that stand out: the peak-demand rule and the peak-interval rule.

Keywords: Game theory; Cost sharing; Job scheduling; Stability (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

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

Related works:
Working Paper: Stability and fairness in the job scheduling problem (2018)
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:gamebe:v:117:y:2019:i:c:p:1-14

DOI: 10.1016/j.geb.2019.06.006

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().