Multi-objective Scheduling onto Heterogeneous Processors System Using Ant System & Fuzzy Logic Controller

Noureddine Liouane, Hedi Yahia
Ecole Nationale d’Ingénieurs de Monastir
rue Ibn El Jazzar, 5019 Monastir, Tunisie

Pierre Borne
LAGIS, Ecole Centrale de Lille
BP 48, 59651 Villeneuve d’Ascq Cedex, France

Abstract:

In recent years, the static and the dynamic jobs scheduling onto heterogeneous processors present a very well studied problem. Typically the Data Grid Scheduling problem (DGS) has recently become an active research area. The heterogeneous processors scheduling problem (HPSP) can be formulated in several ways and the efficient scheduling of the HPSP on the available resources is one of the key factors for achieving high performance results. Historically, finding an optimal schedule was an NP-hard problem in practical cases; researchers have resorted to devising efficient Heuristics and methods inspired by Nature’s Laws. Moreover, the multi-objective scheduling research derives its importance from the need to address the real world of the heterogeneous processors application, which rarely has a single objective function. A schedule that is of a high-quality for one objective function may in fact be quite insignificant for another. Decision makers must carefully evaluate the compromise involved in considering several different criteria in practical scheduling applications. In this paper, we introduce a new hybrid approach that combines ant system optimisation and fuzzy logic concept to facilitate the multi-objective HPSP optimisation, such as the makspean, and the processors workload. Based on the concept of the ant system and fuzzy controller, we automatically control the ant system parameters evolution for the multi-objective HPSP optimisation.

The simulation results indicate that the combination of the ant system approach and the fuzzy controller is not only an efficient metaheuristic tool when we search a multi-objective schedules under constraints but also significantly surpasses other scheduling approaches in terms of quality and solution cost.

Keywords:

Ant system, fuzzy logic controller, job scheduling, heterogeneous processors, computational grid, large size instances.

Noureddine Liouane was born in Kairouan, Tunisia, in 1963. He received the Master degree of science electrical genius in 1988 from the ENSET-Tunis. He received the PhD degree from Ecole Centrale de Lille, France, in 1998. He is currently “Maitre Assistant” in the ENIM-Monastir and Director of the ISSAT-Kairouan. His research is related to the evolutionary optimisation methods for discrete events systems, computer science and operational research.

Hedi Yahia was born in EL-GFAI-Kairouan, Tunisia, in 1960. He received the Master degree in electrical engineering from ENSET-Tunis, in 1988. Also, he obtained the Doctor degree from “ENIT-Tunis”, in1999. He is currently “Maitre Assistant” in the ENIM-Monastir. His main research interests include power electronics system design, scheduling protocol communication and industrial network optimisation.

Pierre Borne was born in Corbeil, France in 1944, he received the Master degree of Physics in 1967, the Masters of Electronics, of Mechanics and of Applied Mathematics in 1968. The same year he obtained the Diploma of “Ingénieur IDN” (French “Grande Ecole”). He obtained the PhD in Automatic Control of the University of Lille in 1970 and the DSc of the same University in 1976. He became Doctor Honoris Causa of the Moscow Institute of Electronics and Mathematics (Russia) in 1999 and of the University of Waterloo (Canada) in 2006 He is author or co-author of about 200 Journal articles and book chapters, and of 30 plenary lectures and of more than 250 communications in international conferences. He has been the supervisor of 64 PhD thesis and is author of 20 books . He has been President of the IEEE/SMC society in 2000 and 2001 . He is presently Professor “de classe exceptionnelle” at the Ecole Centrale de Lille and director of the French pluriformations national group of research in Automatic Control.

>>Full text
CITE THIS PAPER AS:
Noureddine LIOUANE, Hedi YAHIA, Pierre BORNE, Multi-objective Scheduling onto Heterogeneous Processors System Using Ant System & Fuzzy Logic Controller, Studies in Informatics and Control, ISSN 1220-1766, vol. 17 (3), pp. 95-106, 2008.

1. Introduction

Real world heterogeneous processors scheduling systems are complex and diversified, thereby finding an optimal multi-objective schedule in practical cases is an NP-hard problem and the heuristic approaches must be used.

Conventionally, scheduling problem exists in two forms: Static modes and dynamic modes. In the static case scheduling (Batch-Mode) the jobs are not scheduled as they arise; but they are collected into a set of jobs for the next batch scheduling. While dynamic scheduling case considers a job for scheduling only once. Furthermore, due to the theoretical and practical importance of the scheduling problem, several approaches issue from the directed acyclic graph theory and the soft computing heuristics have been used to examine this problem, [4, 8, 13, 14, 16]. The objective of the scheduling problem is to assign jobs to processors (matching problem), and arrange the execution order of the jobs assigned to each machine (scheduling problem) so that the minimum time of execution is obtained [3]. In the HPSP system considered here, the jobs are assumed independent, i.e. that no constraints of execution exist between the jobs.

For the resolution of the HPSP problems, there exist two approaches: the heuristic methods and the efficient research algorithms including the hybrid heuristics concept. In the static mode of the HPSP, Braun et al. [3] present eleven heuristics for matching and scheduling a set of independent jobs onto heterogeneous computing environment, and the goal was to minimise the makespan. Particular modern heuristics approaches have been recently presented for the problem, such as the Tabu Search [1], Simulated Annealing [18], Local Search [15, 11], Genetic Algorithms [5, 7,9,13, 16, 20], Particle Swarm Optimization [2], Fuzzy based scheduling [10]. Moreover, the single objective is not sufficient in practical case and the decision-maker has a priori information and intuition regarding the nature of the optimisation to be performed. For example, the minimisation of the makespan may be of primary importance and the balance of the processor workload and the total workload may be of secondary interest.

Work with other NP-hard problems has shown that the multi-objective solutions found by the heuristics can often be improved by the approaches based on soft computing technique. Essentially, we remark the existence of two grand classes of multi-objective optimisation procedures:

The Non Pareto approach, that consists in transforming the multi-objective problem to the mono objective problem based on an aggregation operator that mixes the different objectives into a weighted sum. The weighted sum translates multiple objectives into a single objective value for the schedule opportunity [5].
The Pareto approach is directly based on the Pareto optimisation concept. This approach satisfies two objectives: converge to the Pareto front and also obtain diversified solutions scattered all over the Pareto front [19].Very few researchers have been presented with the multi-objective heterogeneous processors scheduling. The complexity of the problem has a major role to play in this.

In this paper, we propose a new method for finding multi-objective HPSP solutions using metaheuristic based on the Ant system and the Fuzzy Logic Controller (AS-FLC). Moreover the definition of the best bounds and the higher bounds of some criteria are presented. The remainder of this paper is organised as follows. In the next section, we describe the formulation of the heterogeneous processor scheduling problem. A new multi-objective scheduling approach called Ant System and Fuzzy Logic Controller is presented in section 3. The illustrative example and the effectiveness of this approach are illustrated in section 4 and section 5. Finally, section 6 concludes the paper.

6. Conclusion

In this paper, two related approaches are presented, ant system and fuzzy logic controller for multi-objective optimisation techniques (AS-FLC), and this for solving the heterogeneous processors scheduling problem (HPSP). Via the new manner of the definition of the best bounds of the criteria (makespan, workload of processors and Total workload), the results of the reformulated problems show that the AS-FLC metaheuristic can find an optimised multi-objective solution for many different problems, it can be effectively adapted to deal with the multi-objective HPSP in computational grids.

During the simulation phases, the AS-FLC can find a very good quality of solutions for many different problems; moreover it does persist to find the optimum for some classes of the multi-objective HPSP problems. It is, however, fairly robust as even when an optimal solution is not found, generally very good solutions are provided. In conclusion we believe that we have demonstrated that the ant system, when associated with fuzzy logic techniques, can be successfully applied to the heterogeneous processors scheduling problem in grid application. Hence, illustrative examples are provided to summarise the proposed methodology, and verify its effectiveness.

References:

ABRAHAM, A., R. BUYYA, and B. NATH., Nature’s Heuristics for Scheduling Jobs on Computational Grids, in The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), India, 2000.
ABRAHAM, A., H. LIU, W. ZHANG and T.G. CHANG, Job Scheduling on Computational Grids Using Fuzzy Particle Swarm Algorithm, 10th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems, Lecture Notes on Artificial Intelligence 4252: 500-507, Springer, 2006.
BRAUN, T.D. and H. J. SIEGEL, N. BECK, L.L. BÖLÖNI, M. MAHESWARAN, A.I. REUTHER, J.P. ROBERTSON, M.D. THEYS, and B. YAO, A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems, Journal of Parallel and Distributed Computing, 61(6): 810-837, 2001.
CAO, J., D.P. SPOONER, S.A. JARVIS and G.R. NUDD, Grid Load Balancing Using Intelligent Agents, Future Generation Computer Systems, 21(1) : 135-149, 2005.
COCHRAN, J.K., S.M. HORNG, and J.W. FOWLER, A Multi-Population Genetic Algorithm to Solve Multi-Objective Scheduling Problems for Parallel Machines, Computers and Operations Research, 30: 1087-1102, 2003.
DORIGO, M. and T. STÜTZLE, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances, Handbook of metaheuristics, International Series in Operations Research and Management Science, 57: 251-285, 2002.
DI MARTINO, V. and M. MILILOTTI, Sub Optimal Scheduling in a Grid Using Genetic Algorithms, Parallel Computing, 30: 553-565, 2004.
GAO, Y., H. RONG and J.Z. HUANG, Adaptive Grid Job Scheduling with Genetic Algorithms, Future Generation Computer Systems, 21(1): 151-161, 2005.
HAJRI, S., N. LIOUANE, S. HAMMADI and P. BORNE, A Controlled Genetic Algorithms by Fuzzy Logic and Belief Functions for Job-Shop Scheduling, IEEE Transaction on System Man and Cybernetics, 83(1): 812-818, 2000.
KUMAR, K.P., A. AGARWAL, and R. KRISHNAN, Fuzzy Based Resource Management Framework for High throughput Computing, In Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, 555-562, 2004.
LIOUANE, N., I. SAAD, S. HAMMADI and P. BORNE, Ant Systems & Local Search Optimization for Flexible Job Shop Scheduling Production, International Journal of Computers, Communications & Control, 2:174-184, 2007.
MAHESWARAN, M., S. ALI, H.J. SIEGEL, D. HENSGEN, and R.F. FREUND, Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems, Journal of Parallel and Distributed Computing, 59(2):107-131, 1999.
PAGE, J. and J. NAUGHTON, Framework for Task Scheduling in Heterogeneous Distributed Computing Using Genetic Algorithms, Artificial Intelligence Review, 4: 415-429, 2005.
RADULESCU, A. and A.J.C. VAN GEMUND, Low-Cost Task Scheduling for Distributed-Memory Machines, IEEE Transactions on Parallel and Distributed Systems, 13(6): 648-658, 2002.
RITCHIE, G. and J. LEVINE, A Hybrid Ant Algorithm for Scheduling Independent Jobs in Heterogeneous Computing Environments, In 23rd Workshop of the UK Planning and Scheduling Special Interes Group (PLANSIG 2004), 2004.
SHIMIZU, Y., Multiobjective Optimization for Site Location Problems through Hybrid Genetic Algorithm with Neural Networks, J. Chem. Engng, Japan, 32: 51-58, 1999.
TOPCUOGLU, H., S. HARIRI, and M. WU, Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, 13(3):260-274, 2002.
YARKHAN, A. and J. DONGARRA, Experiments with Scheduling Using Simulated Annealing in a Grid Environment, in 3rd International Workshop on Grid Computing (GRID2002), 232-242, 2002.
ZITZLER, E., and L. THIELE, Multi-objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation, 4: 257-271, 1999.
ZOMAYA, A.Y. and Y.H. TEH., Observations on Using Genetic Algorithms for Dynamic Load-Balancing, IEEE Transactions On Parallel and Distributed Systems, 12(9):899-911, 2001.