Empirical evaluation of some scheduling lower bound estimation heuristics

Dalkilic M. E. , DINDIR R.

13th International Symposium on Computer and Information Sciences (ISCIS 98), BELEK ANTALYA, Turkey, 26 - 28 October 1998, vol.53, pp.270-277 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 53
  • Country: Turkey
  • Page Numbers: pp.270-277


Tight lower bound estimations are essential to provide a good quality measure of a scheduling algorithm because optimal solutions are usually too expensive to compute. In this paper, we evaluate a subset of the heuristics proposed for estimating the lower bound performance of data path schedules. Our goal is to compare these heuristics on a common platform and quantify the quality of results produced by them. First, we described the Greedy, Recursive, Frame Analysis, and Active Range lower bound estimation heuristics. We, then, defined an experimental test-bed for evaluating these heuristics. Results of the experiments indicate that the Frame Analysis heuristic stands out, both in terms of solution quality and execution speed.