License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.31
URN: urn:nbn:de:0030-drops-78453
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7845/
Go to the corresponding LIPIcs Volume Portal

Das, Syamantak ; Wiese, Andreas

On Minimizing the Makespan When Some Jobs Cannot Be Assigned on the Same Machine

pdf-format:
LIPIcs-ESA-2017-31.pdf (0.6 MB)

Abstract

We study the classical scheduling problem of assigning jobs to machines in order to minimize the makespan. It is well-studied and admits an EPTAS on identical machines and a (2-1/m)-approximation algorithm on unrelated machines. In this paper we study a variation in which the input jobs are partitioned into bags and no two jobs from the same bag are allowed to be assigned on the same machine. Such a constraint can easily arise, e.g., due to system stability and redundancy considerations. Unfortunately, as we demonstrate in this paper, the techniques of the above results break down in the presence of these additional constraints.

Our first result is a PTAS for the case of identical machines. It enhances the methods from the known (E)PTASs by a finer classification of the input jobs and careful argumentations why a good schedule exists after enumerating over the large jobs. For unrelated machines, we prove that there can be no (log n)^{1/4-epsilon}-approximation algorithm for the problem for any epsilon > 0, assuming that NP nsubseteq ZPTIME(2^{(log n)^{O(1)}}). This holds even in the restricted assignment setting. However, we identify a special case of the latter in which we can do better: if the same set of machines we give an 8-approximation algorithm. It is based on rounding the LP-relaxation of the problem in phases and adjusting the residual fractional solution after each phase to order to respect the bag constraints.

BibTeX - Entry

@InProceedings{das_et_al:LIPIcs:2017:7845,
  author =	{Syamantak Das and Andreas Wiese},
  title =	{{On Minimizing the Makespan When Some Jobs Cannot Be Assigned on the Same Machine}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7845},
  URN =		{urn:nbn:de:0030-drops-78453},
  doi =		{10.4230/LIPIcs.ESA.2017.31},
  annote =	{Keywords: approximation algorithms, scheduling, makespan minimization}
}

Keywords: approximation algorithms, scheduling, makespan minimization
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI