English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (2): 54-60.doi: 10.15960/j.cnki.issn.1007-6093.2015.02.006

• 运筹学 • 上一篇    下一篇

有关单机两代理排序问题的两个结果

万龙1,*   

  1. 1. 江西财经大学信息管理学院, 南昌 330013
  • 收稿日期:2014-07-07 出版日期:2015-06-15 发布日期:2015-06-15
  • 通讯作者: 万龙 cocu3328@163.com
  • 基金资助:

    国家自然科学专项基金(No. 11426120), 江西省自然科学基金(No. 20142BAB211017), 江西财经大学校级课题(No. 06162015)

Two results for single-machine two-agent scheduling problems

WAN Long1,*   

  1. 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China
  • Received:2014-07-07 Online:2015-06-15 Published:2015-06-15

PDF

1268

被引次数

2

摘要：

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.

关键词: 两代理排序, 算法复杂度, 最优算法

Abstract:

The paper considers two two-agent scheduling problems on a single machine. For the first two-agent scheduling problem, the objective of agent A is to minimize the total weighted completion time of all jobs of agent A while the objective of agent B is to minimize the maximum cost of the jobs of agent B. For the second two-agent scheduling problem, the objective of agent A is to minimize the total completion time of all jobs of agent A while the objective of agent B is to minimize the makespan which is defined as the maximum completion time of all the jobs of agent B. In this paper, we prove that the first problem is NP-hard in the strong sense which improves the current complexity result and design a dynamic programming other than the previous known algorithm for the second problem.

Key words: two-agent scheduling, algorithm complexity, optimal algorithm