> Detailanzeige

Hermelin, Danny [VerfasserIn]; Kubitza, Judith-Madeleine [VerfasserIn]; Shabtay, Dvir [VerfasserIn]; Talmon, Nimrod [VerfasserIn]; Woeginger, Gerhard [VerfasserIn] ; Danny Hermelin and Judith-Madeleine Kubitza and Dvir Shabtay and Nimrod Talmon and Gerhard Woeginger [MitwirkendeR]

Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht
  • Titel: Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
  • Beteiligte: Hermelin, Danny [VerfasserIn]; Kubitza, Judith-Madeleine [VerfasserIn]; Shabtay, Dvir [VerfasserIn]; Talmon, Nimrod [VerfasserIn]; Woeginger, Gerhard [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.IPEC.2015.55
  • Schlagwörter: Multiagent Scheduling ; Parameterized Complexity
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang