SIRALINA: efficient two‐steps heuristic for storage optimisation in single period task scheduling

In this paper, we study the general problem of one‐dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP‐hard (Touati, 2002), solving an exact integer linear programming formulation is too expensive in practice. In this article, we propose an efficient two‐steps heuristic using model’s properties that allows fast computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.