文献类型：期刊文献

英文题名：Analyzing the price of fairness in scheduling problems with two agents

作者：Yu, Jin[1];Liu, Peihai[2];Lu, Xiwen[2];Gu, Manzhan[3]

机构：[1]Shanghai Jiao Tong Univ, Antai Coll Econ & Management, Shanghai 200030, Peoples R China;[2]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China;[3]Shanghai Univ Finance & Econ, Sch Math, Shanghai, Peoples R China

年份：2025

卷号：321

期号：3

起止页码：750

外文期刊名：EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

收录：;EI(收录号：20244517320460);WOS:【SCI-EXPANDED(收录号:WOS:001369975200001)】；

基金：The authors are sincerely grateful to the anonymous referees. This work is supported by the National Nature Science Foundation of China (12371317) .

语种：英文

外文关键词：Scheduling; Price of fairness; Two-agent; Kalai-Smorodinsky fairness; Proportional fairness

摘要：This paper focuses on the price of fairness in several scheduling problems with two agents, each with a set of nonpreemptive jobs, competing to execute their respective jobs on a single machine. Each agent expects to minimize its objective function, which depends on the completion times of its own jobs. Several objective functions are considered, including makespan, total (weighted) completion time and maximum tardiness. We focus on problems in which both agents pursue the same objective function. For each problem, we analyze the price of fairness and the complexity to find the fairness schedules among the Pareto optimal schedules. When the objective functions of both agents are total completion time, we design an algorithm to generate a near-fair solution and analyze its price of fairness.