Agent-based Scheduler for Unrelated Parallel Machines using a load balancing heuristic

Abstract

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.