Mk. Dhodhi et I. Ahmad, TASK TREE SCHEDULING ONTO LINEAR ARRAYS USING TABU SEARCH, IEE proceedings. Computers and digital techniques, 144(5), 1997, pp. 317-323
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.