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.