| 有关单机两代理排序问题的两个结果 |
| |
| 引用本文： | 万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19(2): 54-60. DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.006 |
| |
| 作者姓名： | 万龙 |
| |
| 作者单位： | 1. 江西财经大学信息管理学院, 南昌 330013 |
| |
| 基金项目： | 国家自然科学专项基金，江西省自然科学基金，江西财经大学校级课题 |
| |
| 摘 要： | 研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.
|
| 关 键 词： | 两代理排序 算法复杂度 最优算法 |
| 收稿时间： | 2014-07-07 |
Two results for single-machine two-agent scheduling problems |
| |
| WAN Long. Two results for single-machine two-agent scheduling problems[J]. OR Transactions, 2015, 19(2): 54-60. DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.006 |
| |
| Authors: | WAN Long |
| |
| Affiliation: | 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China |
| |
| 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. |
| |
| Keywords: | two-agent scheduling algorithm complexity optimal algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
