Complexities of Some Problems on Multi-agent Scheduling on a Single Machine  

作　　者：Jin-Jiang Yuan 

机构地区：[1]School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China

出　　处：《Journal of the Operations Research Society of China》2016年第3期379-384,共6页中国运筹学会会刊（英文）

基　　金：the National Natural Science Foundation of China(Nos.11271338 and 71301038);the National Natural Science Foundation of Henan Province(No.15IRTSTHN006).

摘　　要：We study the computational complexities of three problems on multi-agent scheduling on a single machine.Among the three problems,the computational complexities of the first two problems were still open and the last problem was shown to be unary NP-hard in the literature.We show in this paper that the first two problems are unary NP-hard.We also show that the unary NP-hardness proof for the last problem in the literature is invalid,and so,the exact complexity of the problem is still open.

关 键 词：Multi-agent scheduling Competing agents Non-disjoint agents Unary NP-hard 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]