关键词: 排序, 两个代理, 拟多项式时间算法, 动态规划

Abstract: In this paper, two scheduling problems for two-agent scheduling are considered. One is to minimize total tardiness of agent [A], while the number of late jobs must be kept less than or equal to a fixed value. Another is to minimize total weighted completion times of agent [A], while the number of late jobs must be kept less than or equal to a fixed value, where the jobs of agent [A] satisfy the anti-agreeable relation. Some properties of the optimal schedule are provided for the two problems, and it presents pseudo-polynomial time algorithms of the proposed problem, respectively.

Key words: scheduling, two-agent, pseudo-polynomial time algorithm, dynamic programming