Scheduling two competing agents when one agent has significantly fewer jobs

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

doi:10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs

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

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 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 language	English
Title of host publication	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Editors	Thore Husfeldt, Thore Husfeldt, Iyad Kanj
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	55-65
Number of pages	11
ISBN (Electronic)	9783939897927
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2015.55
Publication status	Published - 1 Nov 2015
Event	10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Greece Duration: 16 Sept 2015 → 18 Sept 2015 Conference number: 10 http://algo2015.upatras.gr/ipec

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	43
ISSN (Print)	1868-8969

Conference

Conference	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Abbreviated title	IPEC 2015
Country/Territory	Greece
City	Patras
Period	16/09/15 → 18/09/15
Internet address	http://algo2015.upatras.gr/ipec

Bibliographical note

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

Keywords

Multiagent scheduling
Parameterized complexity

Access to Document

10.4230/LIPIcs.IPEC.2015.55

Cite this

Hermelin, D., Kubitza, J. M., Shabtay, D., Talmon, N., & Woeginger, G. (2015). Scheduling two competing agents when one agent has significantly fewer jobs. In T. Husfeldt, T. Husfeldt, & I. Kanj (Eds.), 10th International Symposium on Parameterized and Exact Computation, IPEC 2015 (pp. 55-65). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 43). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2015.55

Hermelin, Danny ; Kubitza, Judith Madeleine ; Shabtay, Dvir et al. / Scheduling two competing agents when one agent has significantly fewer jobs. 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. editor / Thore Husfeldt ; Thore Husfeldt ; Iyad Kanj. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. pp. 55-65 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{392694ef7b72400a9327a798a96b9e78,

title = "Scheduling two competing agents when one agent has significantly fewer jobs",

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.",

keywords = "Multiagent scheduling, Parameterized complexity",

author = "Danny Hermelin and Kubitza, {Judith Madeleine} and Dvir Shabtay and Nimrod Talmon and Gerhard Woeginger",

note = "Publisher Copyright: {\textcopyright} Danny Hermelin, Judith Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger;.; 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, IPEC 2015 ; Conference date: 16-09-2015 Through 18-09-2015",

year = "2015",

month = nov,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2015.55",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "55--65",

editor = "Thore Husfeldt and Thore Husfeldt and Iyad Kanj",

booktitle = "10th International Symposium on Parameterized and Exact Computation, IPEC 2015",

url = "http://algo2015.upatras.gr/ipec",

}

Hermelin, D, Kubitza, JM, Shabtay, D, Talmon, N & Woeginger, G 2015, Scheduling two competing agents when one agent has significantly fewer jobs. in T Husfeldt, T Husfeldt & I Kanj (eds), 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Leibniz International Proceedings in Informatics, LIPIcs, vol. 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 55-65, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, 16/09/15. https://doi.org/10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs. / Hermelin, Danny; Kubitza, Judith Madeleine; Shabtay, Dvir et al.
10th International Symposium on Parameterized and Exact Computation, IPEC 2015. ed. / Thore Husfeldt; Thore Husfeldt; Iyad Kanj. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. p. 55-65 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 43).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Scheduling two competing agents when one agent has significantly fewer jobs

AU - Hermelin, Danny

AU - Kubitza, Judith Madeleine

AU - Shabtay, Dvir

AU - Talmon, Nimrod

AU - Woeginger, Gerhard

N1 - Conference code: 10

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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.

AB - 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.

KW - Multiagent scheduling

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84958232398&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2015.55

DO - 10.4230/LIPIcs.IPEC.2015.55

M3 - Conference contribution

AN - SCOPUS:84958232398

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 55

EP - 65

BT - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

A2 - Husfeldt, Thore

A2 - Kanj, Iyad

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

Y2 - 16 September 2015 through 18 September 2015

ER -

Hermelin D, Kubitza JM, Shabtay D, Talmon N, Woeginger G. Scheduling two competing agents when one agent has significantly fewer jobs. In Husfeldt T, Husfeldt T, Kanj I, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2015. p. 55-65. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this