A novel task assignment heuristic using local search in distributed computing systems
Rintu Nath, Aitha Nagaraju · 2017
Task assignment in a distributed computing system is a NP-hard problem and a number of heuristics are available for optimal performance. In this paper a novel approach of using local search for satisfiability along with earliest finish time heuristics is proposed. Local search stochastic for satisfiability checking significantly enhance the scheduling performance in terms of make-span and schedule length ratio (SLR). The model is built on heterogeneous earliest finish time (HEFT) heuristics and evaluated through simulation. Empirical results show better performance of this approach compared to iterative greedy algorithm for local search. Key contributions in this paper • Stochastic local search for satisfiability (SAT) is introduced in a task scheduling heuristic • A new task scheduling heuristics Local Search on Critical Path (LSCP) is proposed based on satisfiability in earliest finish time. • Algorithm is tested, extensive simulations are carried out to do performance evaluation and test results are presented