A novel metaheuristic algorithm and utility function for QoS based scheduling in user-centric grid systems

Scheduling dynamically arriving parallel jobs on a grid system is one of the most challenging problems in supercomputer centers. Response time guarantee is one aspect of providing quality of service (QoS) in grids. Jobs are differently charged depending on the response time demanded by the user and the system must provide completion time guarantees. To tackle these challenges, we propose a new type of utility function for defining QoS in user-centric systems. The proposed utility function is a general form of functions in the literature. This function provides customers and system managers with more options to design SLA contracts. Also, its two due dates can make customers more confident and produce more profit for system providers. This paper develops a novel simulated annealing algorithm combined with geometric sampling (GSSA) for scheduling parallel jobs on a grid system. The proposed algorithm is compared with two other methods from the literature using three metrics of total utility, system utilization and the percentage of accepted jobs. The results show that the proposed GSSA algorithm is able to improve the metrics via better use of resources and also through proper acceptance or rejection decisions made on newly arriving jobs.