最小化总完工时间和总延误的两代理公平定价问题  

Price of Fairness in Two-Agent Single-Machine to Minimize the Total Completion Time and the Total Tardiness

作　　者：种贝贝 樊保强 CHONG Beibei;FAN Baoqiang(School of Mathematics and Statistics,Ludong University,Yantai Shandong 264000,China)

机构地区：[1]鲁东大学数学与统计科学学院,山东烟台264000

出　　处：《重庆师范大学学报（自然科学版）》2022年第1期62-71,共10页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.11801251);山东省自然科学基金(No.ZR2021MA071)。

摘　　要：【目的】研究单台机器环境下,一个代理最小化总完工时间而另一个代理最小化总延误的公平定价问题。【方法】每个代理的工件有相同的加工时间,其中:第1个代理的目标是最小化总完工时间,第2个代理的目标是最小化总延误,并且第2个代理的工件拥有不同的交货期;将这一问题分为不同的情形分别进行考虑。【结果】在Pareto排序集合下的KS公平排序可以在线性时间内找到,并且公平定价的值为1/2,举例说明了这个界是紧的。【结论】上述结果对已有文献结果进行了推广,丰富了单台机器环境下两代理排序的公平定价问题的内容。[Purposes]It considers the price of fairness in two-agent scheduling game,in which one agent minimizes total completion time and another agent minimizes total tardiness in a single machine environment.[Methods]Jobs of each agent have the same processing time,where the first agent seeks to minimize the total completion time,the second agent is to minimize the total tardiness,and the second agent’s job has two different delivery times;the problem is analyzed in different cases.[Findings]All of the KS-fairness schedules can be found in logarithmic time,and the price of fairness equals to a half,an instance illustrated the bound is tight.[Conclusions]It generalizes the results which have existed and enriches the content about price of fairness of two agents in single-machine environment.

关 键 词：两代理排序 KS公平 效用函数 公平定价 

分 类 号：O223[理学—运筹学与控制论]