Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (14): 32-36.

Previous Articles     Next Articles

Two-agent scheduling on single machine to minimize number of tardy jobs

ZHANG Xingong, WANG Hui, BAI Shikun   

  1. College of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China
  • Online:2016-07-15 Published:2016-07-18

最小化误工工件个数的两代理单机排序问题

张新功,王  慧,柏世坤   

  1. 重庆师范大学 数学学院,重庆 401331

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

摘要: 针对研究了两代理情形下的单机排序问题,考虑两类问题:一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理[A]的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。

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