Computer Science > Data Structures and Algorithms
[Submitted on 2 Oct 2018 (this version), latest version 1 May 2019 (v2)]
Title:Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times
View PDFAbstract:We investigate the scheduling of $n$ jobs divided into $c$ classes/batches on $m$ identical parallel machines. For every class there is a sequence-independent setup time. This setup is required whenever a machine switches from the processing of one class to another class. The objective is to find a schedule that minimizes the makespan. We give near-linear approximation algorithms for the following problem variants: the non-preemptive problem context where jobs may not be preempted, the preemptive context where jobs may be preempted but not parallelized, as well as the splittable context where jobs may be preempted and parallelized.
We present the first algorithm improving the previously best approximation ratio of $2$ to a better ratio of $3/2$ in the preemptive case. In more detail, for all three flavors we present an approximation ratio $2$ with running time $\mathcal{O}(n)$, ratio $3/2+\epsilon$ in time $\mathcal{O}(n\log 1/\epsilon)$ as well as a ratio of $3/2$. The $(3/2)$-approximate algorithms have different running times. For the non-preemptive case we get time $\mathcal{O}(n\log (n+\Delta))$ where $\Delta$ is the largest value of the input. The splittable approximation needs a running time of $\mathcal{O}(n+c\log(c+m))$ whereas the algorithm for the preemptive context has a running time $\mathcal{O}(n \log (c+m)) \leq \mathcal{O}(n \log n)$. So far, no PTAS is known for the preemptive problem without restrictions, so we make progress towards that question. Recently Jansen et al. found an EPTAS for the splittable and non-preemptive case but with impractical running times exponential in $1/\epsilon$.
Submission history
From: Max Deppert [view email][v1] Tue, 2 Oct 2018 13:14:46 UTC (52 KB)
[v2] Wed, 1 May 2019 17:01:08 UTC (140 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.