TASK TREE SCHEDULING ONTO LINEAR ARRAYS USING TABU SEARCH

Tabu search is a promising optimisation heuristic that has been succes sfully applied to the solution of many combinatorial optimisation prob lems, yielding optimal or near optimal results. An efficient algorithm based on tabu search is presented, designated as TASS, for the proble m of scheduling a tree-like task graph (task tree) onto linear arrays of processors, with the aim of minimising the system response time. Th e linear processor arrays implemented in VLSI/ULSI technology provide an affordable and cost-effective solution for special applications tha t can be represented by task trees. The performance of the proposed ta bu search-based algorithm is evaluated for a set of test problems sele cted from the literature. Comparison of results obtained by the propos ed algorithm with results reported by previous techniques, shows a con siderable improvement in the system response time.