Title: Grid scheduling by bilevel programming: a heuristic approach

Authors: Lucio Bianco; Massimiliano Caramia; Stefano Giordani; Renato Mari

Addresses: Dipartimento di Ingegneria dell'Impresa, Università di Roma 'Tor Vergata', Via del Politecnico, 1 – 00133 Roma, Italy ' Dipartimento di Ingegneria dell'Impresa, Università di Roma 'Tor Vergata', Via del Politecnico, 1 – 00133 Roma, Italy ' Dipartimento di Ingegneria dell'Impresa, Università di Roma 'Tor Vergata', Via del Politecnico, 1 – 00133 Roma, Italy ' Dipartimento di Ingegneria dell'Impresa, Università di Roma 'Tor Vergata', Via del Politecnico, 1 – 00133 Roma, Italy

Abstract: We study the following grid scheduling problem. A set of independent tasks, submitted to a grid external scheduler (ES), has to be assigned to a set of grid computing sites, each one controlled by a local scheduler (LS), for their execution. With each task are associated a release date and a due-date. If the due-date is exceeded, a penalty cost proportional to the tardiness must be paid. If this cost is too high, the ES could prefer to reject the task paying a rejection cost. Indeed, the ES wants to minimise the total cost for rejecting or delaying tasks, while each LS wants to maximise the computational resource usage efficiency. Thus, the problem is modelled by means of bilevel programming, where the decisions of the ES is constrained by those of the LSs, and vice versa. We propose a heuristic algorithm to solve large size instances. Computational results are presented and discussed. [Received 10 October 2012; Revised 19 March 2013; Accepted 30 June 2013]

Keywords: grid computing; resource management; modelling; heuristics; grid scheduling; bilevel programming.

DOI: 10.1504/EJIE.2015.067450

European Journal of Industrial Engineering, 2015 Vol.9 No.1, pp.101 - 125

Published online: 31 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article