2026-09-19T21:31:40Zhttps://dora.dmu.ac.uk/server/oai/request

oai:dora.dmu.ac.uk:2086/176522023-10-18T02:10:15Zcom_2086_2388col_2086_2389

Hybrid Meta-heuristic Algorithms for Static and Dynamic Job Scheduling in Grid Computing Younis, Muhanad Tahrir The term ’grid computing’ is used to describe an infrastructure that connects geographically distributed computers and heterogeneous platforms owned by multiple organizations allowing their computational power, storage capabilities and other resources to be selected and shared. Allocating jobs to computational grid resources in an efficient manner is one of the main challenges facing any grid computing system; this allocation is called job scheduling in grid computing. This thesis studies the application of hybrid meta-heuristics to the job scheduling problem in grid computing, which is recognized as being one of the most important and challenging issues in grid computing environments. Similar to job scheduling in traditional computing systems, this allocation is known to be an NPhard problem. Meta-heuristic approaches such as the Genetic Algorithm (GA), Variable Neighbourhood Search (VNS) and Ant Colony Optimisation (ACO) have all proven their effectiveness in solving different scheduling problems. However, hybridising two or more meta-heuristics shows better performance than applying a stand-alone approach. The new high level meta-heuristic will inherit the best features of the hybridised algorithms, increasing the chances of skipping away from local minima, and hence enhancing the overall performance. In this thesis, the application of VNS for the job scheduling problem in grid computing is introduced. Four new neighbourhood structures, together with a modified local search, are proposed. The proposed VNS is hybridised using two meta-heuristic methods, namely GA and ACO, in loosely and strongly coupled fashions, yielding four new sequential hybrid meta-heuristic algorithms for the problem of static and dynamic single-objective independent batch job scheduling in grid computing. For the static version of the problem, several experiments were carried out to analyse the performance of the proposed schedulers in terms of minimising the makespan using well known benchmarks. The experiments show that the proposed schedulers achieved impressive results compared to other traditional, heuristic and meta-heuristic approaches selected from the bibliography. To model the dynamic version of the problem, a simple simulator, which uses the rescheduling technique, is designed and new problem instances are generated, by using a well-known methodology, to evaluate the performance of the proposed hybrid schedulers. The experimental results show that the use of rescheduling provides significant improvements in terms of the makespan compared to other non-rescheduling approaches. De Montfort University 2018-09 Thesis or dissertation Doctoral PhD en https://www.dora.dmu.ac.uk/handle/2086/17652 https://dora.dmu.ac.uk/bitstreams/48802631-23a5-40d0-9f8d-71440f6f8085/download bd41181d9a4c38b5ebacc69a027024d9 https://dora.dmu.ac.uk/bitstreams/d160e034-6eee-44bb-8089-35a8f46ac2c1/download c731fa15a35f9804f0d2f2a9db0ea215 https://dora.dmu.ac.uk/bitstreams/0355a86c-5fdd-41f2-8230-1930b7f86cfe/download bcba98cfc5516e0a8f6aae1858d9b433 Faculty of Technology