Efficient grid scheduling through the incremental schedule-based approach

Although Grid users demand good performance for their jobs, this requirement is often not satisfied by the widely used queue-based scheduling approaches. This article concentrates on the application of schedule-based methods that improve on both the service delivered to the user and the traditional objective of machine usage. Importantly, the interaction between the incremental application of these methods and the dynamic character of the problem allows reasonable runtimes to be achieved. Two new schedule-based methods that are designed to schedule dynamically arriving jobs on machines in a computational Grid are formally described in the article. The Earliest Gap—Earlier Deadline First (EG-EDF) policy fills the earliest gap in the known schedule with newly arriving jobs, incrementally building a new schedule. If the gap is not suitable for an incoming job, the EDF policy is used to modify the existing schedule. A Tabu search algorithm is used to further optimize the schedule by moving selected jobs into the earliest suitable gaps. The proposed incremental schedule-based methods are compared with some of the most common queue-based scheduling algorithms such as FCFS (First Come First Served), EASY backfilling (Extensible Argonne Scheduler sYstem), Flexible backfilling as well as with the nonincremental version of the EG-EDF schedule-based policy.