在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报

• • 上一篇    下一篇

工件可拒绝的两个代理排序问题的全多项式时间近似方案

冯   琪1,   杨丽华1,   狄   帅2   

  1. 1- 中原工学院理学院，郑州  450007
    2- 京东数字科技，北京  100015
  • 收稿日期:2020-09-18 接受日期:2021-01-14 出版日期:2021-06-15 发布日期:2021-08-15
  • 通讯作者: 冯 琪 E-mail: 5777@zut.edu.cn
  • 基金资助:
    国家自然科学基金 (11701595; 61806184)；河南省高等学校重点科研项目 (20A110037)；中原工学院青年骨干教师项目 (2018XQG15).

A Full Polynomial-time Approximation Scheme of Two-agent Scheduling with Job Rejection

FENG Qi1,   YANG Li-hua1,   DI Shuai2   

  1. 1- College of Science, Zhongyuan University of Technology, Zhengzhou 450007

    2- Jing Dong Digits Technology, Beijing 100015
  • Received:2020-09-18 Accepted:2021-01-14 Online:2021-06-15 Published:2021-08-15
  • Contact: Q. Feng. E-mail address: 5777@zut.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (11701595; 61806184); the Key Research Project of Henan Higher Education Institutions (20A110037); the Young Backbone Teachers Training Program of Zhongyuan University of Technology (2018XQG15).

PDF (PC)

166

摘要： 本文研究单处理机上工件可拒绝的两个代理的排序问题．在此问题中，有两个代理A和B，分别有各自的工件集和费用函数．代理A的工件可以被接收，也可以被拒绝，但要支付一定的拒绝费用．代理B的工件要全部接收．代理A的费用函数是他的接收工件的最大完工时间与拒绝工件的拒绝费用之和，代理B的费用函数是他的工件的最大延迟．排序问题的目标是在满足代理B的费用函数不超过一定数量的前提下，使得代理A的费用函数达到最小．对于该问题给出了一个全多项式时间近似方案．

关键词: 排序, 代理, 拒绝, 近似方案

Abstract: We consider a two-agent scheduling problem with rejection on a single machine. For the problem, we have two agents A and B and each agent has its own job set and cost function. A job of agent A is either accepted or rejected with a certain rejection penalty having to be paid. The jobs of agent B must be accepted. The cost function of agent A is the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. The cost function of agent B is the maximum lateness. The objective of the scheduling problem is to minimize the cost function of agent A, given that the cost function of agent B does not exceed a fixed value. For this problem, we give a full polynomial-time approximation scheme.

Key words: scheduling, agent, rejection, approximation scheme

中图分类号: