: Poetschke, H.; Rosner, S.; Scholles, M.

Abstract
Published scheduling algorithms have a fixed complexity. Hence, a range of different scheduling tools has to be implemented according to whether short scheduling times for prototyping or nearoptimal solutions for real-time computing are required. To overcome this obstacle, a new scheduling algorithm is proposed, which balances computational complexity against the quality of the schedule. This is achieved by evaluating the consequences of a scheduling decision for the next k scheduling steps. Comparisons with the iterative Declustering algorithm and the Dynamic Level list scheduler show that the length of a schedule can be considerably shortened even for a moderate number of look-ahead steps. The best improvements are obtained in the presence of strong resource contention, i.e. when hardware resources are maximally utilized. This observation is very promising for practical applications and may reduce the amount of hardware necessary for a real-time implementation of the application.