{"ID":2883293,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.08979","arxiv_id":"2508.08979","title":"Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee","abstract":"We consider the problem of scheduling $n$ jobs on $m$ uniform machines while minimizing the makespan ($Q||C_{\\max}$) and maximizing the minimum completion time ($Q||C_{\\min}$) in an online setting with migration of jobs. In this online setting, the jobs are inserted or deleted over time, and at each step, the goal is to compute a near-optimal solution while reassigning some jobs, such that the overall processing time of reassigned jobs, called migration, is bounded by some factor $β$ times the processing time of the job added or removed. We propose Efficient Polynomial Time Approximation Schemes (EPTASs) with an additional load error of $\\mathcal{O}(\\varepsilon p_{\\max})$ for both problems, with constant amortized migration factor $β$, where $p_{\\max}$ is the maximum processing time in the instance over all steps. As an intermediate step, we obtain Efficient Parameterized Approximation Schemes (EPASs) for both problems, $(1+\\varepsilon)$-competitive algorithms parameterized by $p_{\\max}$ and the number of different processing times $d$ in an instance, with $β$ bounded in a function of $p_{\\max}$, $d$ and $\\varepsilon$. This is the first result in the direction of a polynomial time approximation scheme in the field of online scheduling with bounded reassignment on uniform machines; before, such results were known only for the considered problems on identical machines. Crucial to our result is a division of the machines into large and small machines depending on the current approximate objective value, allowing for different approaches on either machine set, as well as a new way of rounding the instance that does not depend on the current objective value.","short_abstract":"We consider the problem of scheduling $n$ jobs on $m$ uniform machines while minimizing the makespan ($Q||C_{\\max}$) and maximizing the minimum completion time ($Q||C_{\\min}$) in an online setting with migration of jobs. In this online setting, the jobs are inserted or deleted over time, and at each step, the goal is t...","url_abs":"https://arxiv.org/abs/2508.08979","url_pdf":"https://arxiv.org/pdf/2508.08979v1","authors":"[\"Hauke Brinkop\",\"David Fischer\",\"Klaus Jansen\"]","published":"2025-08-12T14:46:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}