关键词: 双代理排序, 帕累托最优, 公平

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 benefit 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