Fast Multi-objective Rescheduling of Workflows to Constrained Resources Using Heuristics and Memetic Evolution

Abstract

Scheduling of jobs organized in workflows to a computational grid is a permanent
process due to the dynamic nature of the grid and the frequent arrival of
new jobs. Thus, a permanent rescheduling of already planned and
new jobs must be performed. This paper will continue and extend
previous work, which focused on the tuning of our Global
Optimising Resource Broker and
Allocator GORBA in a static planning environment. A formal
definition of the scheduling
problem and a classification will be given. New heuristics for
rescheduling based on the old plan will be introduced and it
will be investigated how they contribute to the overall planning
process. As an extension to the work published in Conf. Proc. PPAM
2009, LNCS 6067 or 6068 (to be published in July, 2010) a simple local search is added to the basic Evolutionary Algorithm
(EA) of GORBA and it is examined, whether and how the resulting Memetic Algorithm
improves the results within the limited time frame of three minutes available
for planning. Furthermore, the maximal possible load, which can be handled within
the given planning time, will be examined for a grid of growing size of up to
7000 grid jobs and 700 resources.