运筹与管理2025，Vol.34Issue(8)：60-65,6.DOI:10.12005/orms.2025.0241
最小加权误工数和最大延误的双代理KS公平定价
Price of KS Fairness in Two-agent for Number of Minimum Weighted Tardy Jobs and Maximum Tardiness
摘要
Abstract
In a multi-agent scheduling problem,where each agent has its own set of jobs and competes to use the same machine,the goal is to find all pareto optimal solutions or a schedule of jobs that maximizes system utility,which is weighted sum of the agent's utilities.However,every agent has its own objective and even a system optimum schedule may be unfair to the worse-off agent.Rather,a schedule that incorporates some criterion of fairness may be more accepted by all agents.In this regard,it is interesting and important to introduce a fair measure for resources distribution in the multi-agent scheduling. This paper discusses the price of fairness under a fairness measure in two-agent scheduling(namely agent A and B)with agent A aiming to minimize the number of weighted tardy jobs and agent B to minimize maximum job tardiness.Note that the maximum job tardiness is determined by the job with the maximum completion time,and the job of agent B will be continuously processed in system optimum schedule.So,assume that agent B has only a long job.The jobs of agent A have different weights and the processing time for all jobs are the same.The price of fairness(PoF)is the maximum relative loss in overall system utility of a fair schedule with respect to the system optimum schedule.The problem is to find a scheduling with respect to a given fair measure and analyse the bound of PoF. Firstly,we investigate the concepts of agent's cost,utility,normalized utility,system utility and Kalai-Smorodinsky fairness(KS).KS fairness arises from the classical max-min fairness,in which the agent's utility is replaced by the normalized utility.The idea of KS fairness is to maximize the normalized utility of the agent who is worst-off.Because Pareto optimality aims to make full use of limited resources and create maximum bene-fit at the minimum cost.This paper considers KS fairness schedules with respect to Pareto optimal schedules.Then we obtain characteristics and optimality properties by analyzing the structure of Pareto optimal schedules and KS fairness schedules.We show that the KS fairness schedules can be found in linear time and provide a tight bound on the PoF of fairness. For further research,it will be interesting to extend the two-agent scheduling model to more general cases,such as different job's processing time and more due dates.Another direction is to study the price of fairness with respect to proportional fairness,and in different agent's objective scenarios,such that both of the two agents want to minimize the maximum tardiness.关键词
双代理排序/帕累托最优/公平Key words
two-agent scheduling/Pareto optimal/KS fairness分类
数理科学引用本文复制引用
刘振旋,樊保强,吴勇芝,刘婷婷,姜燕君..最小加权误工数和最大延误的双代理KS公平定价[J].运筹与管理,2025,34(8):60-65,6.基金项目
国家自然科学基金资助项目(11801251) （11801251）
山东省自然科学基金项目(ZR2021MA071,ZR202211050004) （ZR2021MA071,ZR202211050004）
