Independent And Dependent Job Scheduling Algorithms Based On Weighting Model For Grid Environment - M. Al-Najjar, Hazem (2018)
Grid system has been used to solve complex problems that need years to be executed. One of the issues in improving the performance of a grid system is how to schedule the submitted jobs in an efficient, fast and reliable way. In addition, job scheduling is considered as a NP-hard problem. Therefore, finding the optimal sequence to improve the total execution time and average waiting time will be very difficult and will consume a lot of computational resources. As a result, researchers have tried to improve job scheduling system using multiple algorithms. However, the previous algorithms are complicated and needed a lot of computational resources. Besides that, their works have not considered using job categorical variables in serving jobs as a dominant parameter. This thesis presents job weighting model using a Twostep clustering to assign the categorical and continuous variables of jobs into classes for both independent and dependent job scheduling. After that, ranking equation is used to arrange the generated classes from lightest to heaviest. Moreover, linear regression model with the generated ranking classes is employed into the proposed weighting model. The resulting model is then applied onto the independent and dependent job scheduling algorithms to verify the capability of proposed job scheduling model in a real environment. To validate the capability of the proposed weighting model which aims to improve independent job scheduling, a combination between job weight value and job ranking backfilling is considered. On the other hand, a job weight is combined with a graph of dependent jobs to improve dependent job scheduling. By simulation, independent job scheduling algorithm showed improvement in total execution time and average waiting time which is equal to 1.13 and 7.12 times, respectively. For the dependent algorithm, the results outperform the previous algorithms in total execution time and average waiting time, the improvement is 1.31 and 3.05 times, respectively. The results have demonstrated that the categorical and continuous variables of jobs can be used to improve the total execution time and average waiting time of job scheduling algorithms with less overhead in a real environment.