文献类型：期刊文献

英文题名：Approximation schemes for two-agent scheduling on parallel machines

作者：Zhao, Kejun[1];Lu, Xiwen[1]

机构：[1]E China Univ Sci & Technol, Sch Sci, Dept Math, Shanghai 200237, Peoples R China

年份：2013

卷号：468

起止页码：114

外文期刊名：THEORETICAL COMPUTER SCIENCE

收录：;EI(收录号：20130115856389);WOS:【SCI-EXPANDED(收录号:WOS:000313917200011)】；

基金：This research is supported in part by the National Nature Science Foundation of China (No. 11071072) and the Fundamental Research Funds for the Central Universities WH1013016.

语种：英文

外文关键词：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. (C) 2012 Elsevier B.V. All rights reserved.