{"ID":2880171,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14528","arxiv_id":"2508.14528","title":"A $(4/3+\\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times","abstract":"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 \u003c 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.","short_abstract":"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 s...","url_abs":"https://arxiv.org/abs/2508.14528","url_pdf":"https://arxiv.org/pdf/2508.14528v1","authors":"[\"Max A. Deppert\",\"David Fischer\",\"Klaus Jansen\"]","published":"2025-08-20T08:37:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}