License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.55
URN: urn:nbn:de:0030-drops-55713
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5571/
Go to the corresponding LIPIcs Volume Portal

Hermelin, Danny ; Kubitza, Judith-Madeleine ; Shabtay, Dvir ; Talmon, Nimrod ; Woeginger, Gerhard

Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs

pdf-format:
8.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{hermelin_et_al:LIPIcs:2015:5571,
  author =	{Danny Hermelin and Judith-Madeleine Kubitza and Dvir Shabtay and Nimrod Talmon and Gerhard Woeginger},
  title =	{{Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5571},
  URN =		{urn:nbn:de:0030-drops-55713},
  doi =		{10.4230/LIPIcs.IPEC.2015.55},
  annote =	{Keywords: Parameterized Complexity, Multiagent Scheduling}
}

Keywords: Parameterized Complexity, Multiagent Scheduling
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI