{"ID":2892167,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.15434","arxiv_id":"2507.15434","title":"Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling","abstract":"We are concerned with the problem of scheduling $n$ jobs onto $m$ identical machines. Each machine has to be in operation for a prescribed time, and the objective is to minimize the total machine working time. Precisely, let $c_i$ be the prescribed time for machine $i$, where $i\\in[m]$, and $p_j$ be the processing time for job $j$, where $j\\in[n]$. The problem asks for a schedule $σ\\colon\\, J\\to M$ such that $\\sum_{i=1}^m\\max\\{c_i, \\sum_{j\\inσ^{-1}(i)}p_j\\}$ is minimized, where $J$ and $M$ denote the sets of jobs and machines, respectively. We show that First Fit Decreasing (FFD) leads to a $1.5$-approximation, and this problem admits a polynomial-time approximation scheme (PTAS). The idea is further applied to mixed-criticality system scheduling to yield improved approximation results.","short_abstract":"We are concerned with the problem of scheduling $n$ jobs onto $m$ identical machines. Each machine has to be in operation for a prescribed time, and the objective is to minimize the total machine working time. Precisely, let $c_i$ be the prescribed time for machine $i$, where $i\\in[m]$, and $p_j$ be the processing time...","url_abs":"https://arxiv.org/abs/2507.15434","url_pdf":"https://arxiv.org/pdf/2507.15434v1","authors":"[\"Yi-Ting Hsieh\",\"Mong-Jen Kao\",\"Jhong-Yun Liu\",\"Hung-Lung Wang\"]","published":"2025-07-21T09:45:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}