Comparison among four Modified Discrete Particle Swarm Optimization for Task Scheduling in Heterogeneous Computing Systems
S.Sarathambekai1, K.Umamaheswari2
1S.Sarathambekai, Assistant Professor, Department of IT/ PSG College of Technology/ Coimbatore, Tamilnadu, India
2Dr.K. Umamaheswari, Professor, Department of IT/ PSG College of Technology/ Coimbatore, Tamilnadu, India
Manuscript received on April 05, 2013. | Revised Manuscript received on April 28, 2013. | Manuscript published on May 05, 2013. | PP: 371-379 | Volume-3, Issue-2, May 2013. | Retrieval Number: B1568053213/2013©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Task scheduling in heterogeneous multiprocessor systems is an extremely hard NP complete problem. Hence, the heuristic approaches must be used to discover good solutions within a reasonable time. Particle Swarm Optimization (PSO) is a population based new heuristic optimization technique developed from swarm intelligence. This paper presents a Modified Discrete PSO (MDPSO). PSO was originally designed for continuous optimization problems. Some conversion techniques are needed to operate PSO in discrete domain. In Discrete PSO, conversion techniques are not required. Here, the particles are directly represented as integer vectors. The MDPSO extends the basic form of DPSO which incorporates mutation, which is an operator of Genetic Algorithm, for the better diversity of the particles. In this paper, the scheduler aims at minimizing make span, reliability cost and flow time in heterogeneous multiprocessor systems for scheduling of independent tasks using four different MDPSO algorithms. The performance of PSO greatly depends on its control parameters such as inertia weight and acceleration coefficients. Slightly different parameter settings may direct to very different performance. This paper compares the formulation and results of four different MDPSO techniques: constant control parameters, random inertia weight with time varying acceleration coefficients, linearly decreasing inertia weight with time varying acceleration coefficients and constant control parameters with dependent random parameters. Benchmark instances of Expected Time to Complete (ETC) model is used to test the MDPSO. Based on this comparative analysis, MDPSO with linearly decreasing inertia weight provides better results than others.
Keywords: Expected Time to Complete, Heterogeneous Multiprocessor systems, Task Scheduling, Particle Swarm Optimization.