A linear programming-driven genetic algorithm for meta-scheduling on utility grids

In Grids, single user-based brokers focus on meeting individual user job's quality of service requirements such as minimising the cost and time without considering demands from other users. This results in contention for resources and suboptimal schedules. Meta-scheduling in Grids aims to address this scheduling problem, which is NP-hard due to its combinatorial nature. Thus, many heuristic-based solutions using genetic algorithm (GA) have been proposed, apart from traditional algorithms such as greedy and first come first serve. In this paper, we propose the need for a ‘meta-brokering system’ and present a Meta-Broker which schedules multiple jobs on utility Grids. First, we present the architecture of our Meta-Broker and discuss the requirements and functionalities of the Meta-Broker. We, then, propose a linear programming (LP)/integer programming model for scheduling user jobs to multiple resources. We also propose a novel algorithm LP-driven GA which combines the capabilities of LP and GA. The aim of this algorithm is to obtain the best meta-schedule that minimises the combined cost of all users in a coordinated manner. Simulation results show that in comparison to single user-based brokers such as Gridbus and GRUBER, our proposed integrated algorithm offers the best schedule having the minimum processing cost with negligible time overhead.