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, Türkiye, 26 - 28 Ekim 1998, cilt.53, ss.270-277 identifier

  • Cilt numarası: 53
  • Basıldığı Şehir: BELEK ANTALYA
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.270-277

Özet

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.