Independent And Dependent Job Scheduling Algorithms Based On Weighting Model For Grid Environment
Loading...
Date
2018-06-01
Authors
M. Al-Najjar, Hazem
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
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.