Scientific Research and Essays

  • Abbreviation: Sci. Res. Essays
  • Language: English
  • ISSN: 1992-2248
  • DOI: 10.5897/SRE
  • Start Year: 2006
  • Published Articles: 2758

Full Length Research Paper

Hybrid intelligent algorithm [improved particle swarm optimization (PSO) with ant colony optimization (ACO)] for multiprocessor job scheduling

K. Thanushkodi1 and K. Deeba2*
  1Akshaya College of Engineering, Anna University of Technology, Coimbatore, India. 2Department of Computer Science and Engineering, Kalignar Karunanidhi Institute of Technology, Anna University of Technology, Coimbatore, India.
Email: [email protected]

  •  Accepted: 03 May 2012
  •  Published: 30 May 2012

Abstract

 

Efficient multiprocessor scheduling is essentially the problem of allocating a set of computational jobs to a set of processors to minimize the overall execution time. The main issue is how jobs are partitioned in which total finishing time and waiting time is minimized. Minimization of these two criteria simultaneously, is a multi objective optimization problem. There are many variations of this problem, most of which are NP-hard problem, so we must rely on heuristics to solve the problem instances. Many heuristic-based approaches have been applied to finding schedules that minimize the execution time of computing tasks on parallel processors. Particle swarm optimization (PSO) is currently employed in several optimization and search problems due to its ease and ability to find solutions successfully. A variant of PSO, called as improved particle swarm optimization (ImPSO) has been developed in this paper and is hybridized with the ant colony optimization (ACO) to achieve better solutions. The proposed hybrid algorithm effectively exploits the capabilities of distributed and parallel computing of swarm intelligence approaches. In addition hybrid algorithm using improved particle swarm optimization (ImPSO) with artificial immune system (AIS) is also implemented for the same set of problems to compare with the proposed hybrid algorithm (ImPSO with ACO). It was observed that the proposed hybrid approach (Improved PSO with ACO) gives better results in experiments and reduces finishing and waiting time simultaneously.

 

Key words: Particle swarm optimization (PSO), improved particle swarm optimization (ImPSO), ant colony optimization (ACO), job scheduling, finishing time, waiting time.