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 $\ddot{I}ƒ:J\to M$ such that ${\sum }_{i=1}^m\max \{c_i,{\sum }_{j\in \ddot{I}{ƒ}^{-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.