Scheduling two competing agents when one agent has significantly fewer jobs

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Titel10th International Symposium on Parameterized and Exact Computation, IPEC 2015
RedacteurenThore Husfeldt, Thore Husfeldt, Iyad Kanj
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's55-65
Aantal pagina's11
ISBN van elektronische versie9783939897927
DOI's
StatusGepubliceerd - 1 nov 2015
Evenement10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Griekenland
Duur: 16 sep 201518 sep 2015

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume43
ISSN van geprinte versie1868-8969

Congres

Congres10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Land/RegioGriekenland
StadPatras
Periode16/09/1518/09/15

Bibliografische nota

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

Vingerafdruk

Duik in de onderzoeksthema's van 'Scheduling two competing agents when one agent has significantly fewer jobs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit