## 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 | |

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 |

### Bibliographical note

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

## Keywords

- Multiagent scheduling
- Parameterized complexity