An Improved Job Scheduling Algorithm For The Computational Grid Environment

Abstract

Grid is a dynamically shared environment It comprises of newlinegeographically distributed heterogeneous computational resources of multiinstitutional newlinedomains with different usage policies The idle resources of newlinemultiinstitutional domains form a virtual organization The virtual newlineorganization provides coordinated resource sharing to solve complex newlinescientific problems that require enormous computing power newlineScheduling is a difficult problem of the grid Scheduling problem is newlinea Nondeterministic Polynomial NPhard problem Computing optimal newlinesolution for NPhard problem is intractable The reasonable assumptions are newlinedifficult to find an optimal solution due to the dynamic grid nature Hence newlineheuristic algorithms provide good solutions newlineThe objective of grid scheduling is to find a feasible schedule that newlineminimizes the scheduling criteria the makespan Makespan is the overall newlinecompletion time of all the jobs submitted in the grid Heuristic approach newlineproves to be the efficient approach for solving the computationally hard newlineproblems The heuristic approach includes Minimum Completion Time newlineMCT Opportunistic Load Balancing OLB Maxmin Minmin and newlineGenetic Algorithm GA The Minmin heuristic performs well compare to newlinethe other heuristic techniques newlineThis thesis proposes three different approaches to minimize the newlinemakespan of grid scheduling The first approach uses heuristic techniques and newlineimplements on the basis of Minmin algorithm To reduce the makespan and newlineimprove resource utilization the first approach includes three different newlineheuristic algorithms Minmean Improved Minmean and Enhanced Minmean newlinein grid scheduling The proposed heuristic scheduling algorithms works newlinein two phases In phase 1 the algorithm allocates the jobs to the machines newlinebased on Minmin algorithm In phase 2 the algorithm calculates the mean newlinecompletion time and it selects the machine whose completion time is greater newlinethan mean completion time The algorithm reschedules the tasks assigned on newlinethe selected resources to the resource newline newline