Stability and fairness in the job scheduling problem

• 成果类型: Article
• 署名作者: Bahel, Eric; Trudeau, Christian
• 署名单位: Virginia Polytechnic Institute & State University; University of Windsor
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2019.06.006
• 发表日期: 2019
• 页码: 1-14
• 关键词: Game theory; cost sharing; Job scheduling; STABILITY

摘要

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. (C) 2019 Elsevier Inc. All rights reserved.