摘要
【目的】研究单台机器环境下,一个代理最小化总完工时间而另一个代理最小化总延误的公平定价问题。【方法】每个代理的工件有相同的加工时间,其中:第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.
作者
种贝贝
樊保强
CHONG Beibei;FAN Baoqiang(School of Mathematics and Statistics,Ludong University,Yantai Shandong 264000,China)
出处
《重庆师范大学学报（自然科学版）》
CAS
北大核心
2022年第1期62-71,共10页
Journal of Chongqing Normal University:Natural Science
基金
国家自然科学基金(No.11801251)
山东省自然科学基金(No.ZR2021MA071)。
