A Fully Polynomial Time Approximation Scheme for Adaptive Variable Rate Task Demand

The Adaptive Variable Rate (AVR) task model defines a task where job WCET and period are a function of engine speed. Motivated by a lack of tractable AVR task demand methods, this work uses predefined job sequences for the Bounded Precedence Constraint Knapsack Problem inherent in AVR task demand calculation instead of enumerating all considered speeds as in existing work. A new, exact approach is proposed and approximated, enabling the derivation of a Fully Polynomial Time Approximation Scheme that outperforms the state-of-the-art in runtime (7,800x improvement) and RAM use (99% reduction) with less than 8% demand overestimate.