Scheduling two competing agents when one agent has significantly fewer jobs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Title of host publication10th International Symposium on Parameterized and Exact Computation, IPEC 2015
EditorsThore Husfeldt, Thore Husfeldt, Iyad Kanj
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages55-65
Number of pages11
ISBN (Electronic)9783939897927
DOIs
Publication statusPublished - 1 Nov 2015
Event10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Greece
Duration: 16 Sep 201518 Sep 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume43
ISSN (Print)1868-8969

Conference

Conference10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Country/TerritoryGreece
CityPatras
Period16/09/1518/09/15

Bibliographical note

Publisher Copyright:
© Danny Hermelin, Judith Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger;.

Keywords

  • Multiagent scheduling
  • Parameterized complexity

Fingerprint

Dive into the research topics of 'Scheduling two competing agents when one agent has significantly fewer jobs'. Together they form a unique fingerprint.

Cite this