Lower-Bound Estimation of Functional Units in Time-Constrained Scheduling

In this paper,the problem of lower-bound estimation on functional units for the time-constrained scheduling is studied.Two polynomial estimators,UnitLength and MaxFlow,are proposed.The main idea of the two algorithms is to transform the original scheduling problem into new problems by relaxing constraints,and guarantee that the optimal solutions of the new problems are lower-bounds of the original problem.The existing MinInterval method and an integer linear programming formulation are implemented to evaluate the accuracy of the proposed algorithms.Experimental results indicate that the runtime of the two estimators is reasonable,and UnitLength is more accurate than MinInterval.Finally,the effect of relaxation of different constraints on the estimation accuracy is concluded.