Agent-based Scheduler for Unrelated Parallel Machines using a load balancing heuristic
View/ Open
Date
2009Author
Opiyo,E T O
Ayienga, Eric
Okello-Odongo, William
Type
ArticleLanguage
enMetadata
Show full item recordAbstract
The problem of finding an optimal schedule for n independent jobs on m non-identical machines is considered.
Several solutions to this problem have been proposed but most of them do not scale well due to the large schedule
spaces that are involved. This paper presents a load balancing heuristic that is used by agents that represent jobs as
they select the machines. The load balancing heuristic is the dominant agent selection policy but its effectiveness
has been explored through combining it with other heuristics. These heuristics are partial mutation of jobs (PM),
smallest jobs first (SJF) or largest jobs first (LJF). The makespan is the total time it takes to execute all the jobs. It
is used to evaluate the schedules with preference given to the schedule with the least makepan. The optimal
schedule is the one with the least makespan. Ways of generating optimal or near optimal schedules are explored
using some concrete schedule spaces that are very large. The simulation results show that when the load balancing
heuristic is used, combined with the heuristic in which the jobs are arranged in descending order (LJF) then better
schedules generally result. Better schedules are those with the minimal makespan. The effort required to produce
optimal or near optimal schedules is minimal given that only one scheduling pass is required to generate the
schedule. Such a heuristic holds much promise for scheduling or resource allocation tasks in dynamic
environments such as grid computing.
Publisher
School of Computing and Informatics