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

Two results for single-machine two-agent scheduling problems

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

The paper considers two two-agent scheduling problems on a single ma- chine. 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.