Small-World Optimization Applied to Job Scheduling on Grid Environments from a Multi-Objective Perspective


Abstract

Grid scheduling techniques are widely studied in the related literature to fulfill scientist requirements of deadline or budget for their experiments. Due to the conflictive nature of these requirements - minimum response time usually implies expensive resources - a multi-objective approach is implemented to solve this problem. In this paper, we present the Multi-Objective Small World Optimization (MOSWO) as a multi-objective adaptation from algorithms based on the small world phenomenon. This novel algorithm exploits the so-called small-world effect from complex networks, to optimize the job scheduling on Grid environments. Our algorithm has been compared with the well-known multi-objective algorithm Non-dominated Sorting Genetic Algorithm-II (NSGA-II) to evaluate the multi-objective properties and prove its reliability. Moreover, MOSWO has been compared with real schedulers, the Workload Management System (WMS) from gLite and the Deadline Budget Constraint (DBC) from Nimrod-G, improving their results.