文章基本信息

标题：Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
本地全文：下载
作者：Danny Hermelin ; Judith-Madeleine Kubitza ; Dvir Shabtay 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：43
页码：55-65
DOI：10.4230/LIPIcs.IPEC.2015.55
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.
关键词：Parameterized Complexity; Multiagent Scheduling