Lower bound on general minimal resource interval scheduling with arbitrary component selection

Abstract

Exploring lower bound of scheduling is an important problem in high-level synthesis. In this paper, we address the problem of computing lower bound on the general minimal resource interval scheduling problem, called n-n-MRIS, in which arbitrary component selections are allowed in stead of the traditional uni-component selection. The problem of n-n-MRIS is proved to be strongly NP hard. An efficient ILP model and a surrogate relaxation technique are proposed to produce a lower bound for the n-n-MRIS problem.