Article ID: | iaor20073269 |
Country: | Greece |
Volume: | 4 |
Issue: | 3 |
Publication Date: | Sep 2004 |
Journal: | Operational Research - An International Journal |
Authors: | Savvas I.K., Kechadi M-Tahar |
Keywords: | heuristics: tabu search |
In this paper, we study the problem of scheduling a large number of time-consuming tasks (of different sizes) on a heterogeneous distributed system. The heterogeneity is expressed in terms of the inter-resources communication and of the resource latency. In such systems, balancing the load of the tasks among the resources is very critical, since the time spent by a task in the system is considered as the main issue that needs to be minimised. We propose a task scheduling technique, which consists of two heuristic algorithms, namely Recursive Neighbour Search (RNS) and Augmented Tabu-Search (ATS). Our techniques do not address directly the load-balancing problem since it may be unrealistic in such large environments, but we will show that even a non-perfectly load-balanced system can behave reasonably well by taking into account the tasks' time demands. These algorithms are compared to well-known scheduling algorithms (Eager's Random and Threshold policy algorithms) in order to study their performance.