Approximation schemes for two-agent scheduling on parallel machines

作者：Zhao, Kejun; Lu, Xiwen^*

来源：Theoretical Computer Science, 2013, 468: 114-121.

DOI：10.1016/j.tcs.2012.11.002

• Agent scheduling
• Parallel machines
• Algorithm
• Dynamic programming
• Fully polynomial time approximation scheme

Two models of two-agent scheduling problem on identical machines are considered in this paper. In both models, the goal is to minimize the makespan and the total completion time of agent A respectively, subject to an upper bound on the makespan of agent B. We prove that these two problems are NP-hard and can be solved in pseudo-polynomial time. Furthermore, we design the fully polynomial time approximation schemes for both problems, respectively.

• 出版日期2013-1-14
• 单位华东理工大学