Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling

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 $\sigma\colon\, J\to M$ such that $\sum_{i=1}^m\max\{c_i, \sum_{j\in\sigma^{-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.