Abstract: This paper considers two-agent scheduling with release times where agent A and agent B have to share m parallel machines for processing their jobs. The objective of agent A is to minimize the total completion time, while the objective of agent B is to ensure its total completion time under a fixed value. Firstly, the considered problem is proved to be NP-hard under the single machine condition. Secondly, a pseudo-polynomial-time algorithm is proposed by using the dynamic programming (DP) method, and then a fully polynomial-time approximation algorithm is further provided.

Key words: Scheduling, two-agent, dynamic programming；pseudo-polynomial-time algorithm, fully polynomial-time approximation algorithm

摘要： 研究了并行机情形下工件带释放时间的双代理调度问题及其求解方法，问题的优化目标为在代理B的工件总完工时间不超过一定值情况下最小化代理A的总完工时间。首先，证明了在单机条件下该问题即为NP-难问题；然后，采用动态规划方法分别给出了求解问题的拟多项式时间算法，并进一步给出了完全近似算法。

关键词: 调度, 双代理, 动态规划, 拟多项式时间算法, 完全近似算法