Premium
Grid scheduling by on‐line rectangle packing
Author(s) -
Caramia Massimiliano,
Giordani Stefano,
Iovanella Antonio
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20021
Subject(s) - rectangle , computer science , grid , scheduling (production processes) , benchmark (surveying) , bin packing problem , distributed computing , packing problems , grid computing , schedule , mathematical optimization , algorithm , mathematics , geometry , geodesy , bin , geography , operating system
The Grid computing paradigm is originated from a new computing infrastructure for scientific research and cooperation, and is becoming an established technology for large‐scale resource sharing and distributed integration. Two main problems arise: how to efficiently allocate resources to tasks and, after this, how to schedule them. In this article we propose to solve the scheduling phase by means of rectangle packing algorithms. In particular, two on‐line rectangle packing algorithms are proposed with the objective of maximizing the system efficiency. A wide computational analysis is provided. The performances of the proposed algorithms are first compared with those of known algorithms on benchmark instances for rectangle packing, and then are evaluated on different Grid scheduling scenarios associated with different processing and dataset environments. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol.44(2), 106–119 2004