A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918127797796864 |
|---|---|
| author | Deppert, Max A. Fischer, David Jansen, Klaus |
| author_facet | Deppert, Max A. Fischer, David Jansen, Klaus |
| contents | We consider the $\mathcal{NP}$-hard problem $\mathrm{P} \mathbf{\vert} \mathrm{pmtn, setup=s_i} \mathbf{\vert} \mathrm{C_{\max}}$, the problem of scheduling $n$ jobs, which are divided into $c$ classes, on $m$ identical parallel machines while allowing preemption. For each class $i$ of the $c$ classes, we are given a setup time $s_i$ that is required to be scheduled whenever a machine switches from processing a job of one class to a job from another class. The goal is to find a schedule that minimizes the makespan.
We give a $(4/3+\varepsilon)$-approximate algorithm with run time in $\mathcal{O}(n^2 \log(1/\varepsilon))$. For any $\varepsilon < 1/6$, this improves upon the previously best known approximation ratio of $3/2$ for this problem.
Our main technical contributions are as follows. We first partition any instance into an "easy" and a "hard" part, such that a $4/3 T$-approximation for the former is easy to compute for some given makespan $T$. We then proceed to show our main structural result, namely that there always exists a $4/3 T$-approximation for any instance that has a solution with makespan $T$, where the hard part has some easy to compute properties. Finally, we obtain an algorithm that computes a $(4/3+\varepsilon)$-approximation in time n $\mathcal{O}(n^2 \log(1/\varepsilon))$ for general instances by computing solutions with the previously shown structural properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14528 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times Deppert, Max A. Fischer, David Jansen, Klaus Data Structures and Algorithms We consider the $\mathcal{NP}$-hard problem $\mathrm{P} \mathbf{\vert} \mathrm{pmtn, setup=s_i} \mathbf{\vert} \mathrm{C_{\max}}$, the problem of scheduling $n$ jobs, which are divided into $c$ classes, on $m$ identical parallel machines while allowing preemption. For each class $i$ of the $c$ classes, we are given a setup time $s_i$ that is required to be scheduled whenever a machine switches from processing a job of one class to a job from another class. The goal is to find a schedule that minimizes the makespan. We give a $(4/3+\varepsilon)$-approximate algorithm with run time in $\mathcal{O}(n^2 \log(1/\varepsilon))$. For any $\varepsilon < 1/6$, this improves upon the previously best known approximation ratio of $3/2$ for this problem. Our main technical contributions are as follows. We first partition any instance into an "easy" and a "hard" part, such that a $4/3 T$-approximation for the former is easy to compute for some given makespan $T$. We then proceed to show our main structural result, namely that there always exists a $4/3 T$-approximation for any instance that has a solution with makespan $T$, where the hard part has some easy to compute properties. Finally, we obtain an algorithm that computes a $(4/3+\varepsilon)$-approximation in time n $\mathcal{O}(n^2 \log(1/\varepsilon))$ for general instances by computing solutions with the previously shown structural properties. |
| title | A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.14528 |