文献类型：期刊文献

英文题名：A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

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

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

年份：2016

卷号：19

期号：1

起止页码：21

外文期刊名：JOURNAL OF SCHEDULING

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

基金：The authors would like to thank the editor and anonymous referees for their helpful comments and suggestions which significantly improve the results and presentation of this paper. This research is supported by National Natural Science of China (11371137, 11201282) and the Fund for the Doctoral Program of China (20120074110021).

语种：英文

外文关键词：Multi-agent scheduling; Identical machines; Makespan; Approximation algorithm; Performance ratio vector

摘要：This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent's objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than for the ith completed agent. Moreover, we show that the performance ratio is tight.