Application of Discrete Particle Swarm Optimization for Grid Task Scheduling Problem

- Application of Discrete Particle Swarm Optimization for Grid Task Scheduling Problem.
- Many applications involve the concepts of scheduling, such as communications, packet routing, production planning [Zhai et al., 2006], classroom arrangement [Mathaisel &.
- Comm, 1991], aircrew scheduling [Chang, 2002], nurse scheduling [Ohki et al., 2006], food industrial [Simeonov &.
- Fonseca, 1993], resource-constrained scheduling problem [Chen, 2007] and grid computing.
- However, in this work, the studied grid task scheduling problem is much more complex than above stated classic task scheduling problems.
- Restated, a grid application is regarded as a task scheduling problem involving tasks with inter-communication and distributed homogeneous or heterogeneous resources, and can be represented by a task interaction graph (TIG)..
- A grid is a collaborative environment in which one or more tasks can be submitted without knowing where the resources are or even who owns the resources [Foster et al., 2001].
- The efficiency and effectiveness of grid resource management greatly depend on the scheduling algorithm [Lee et al., 2007].
- Generally, in the grid environment, these resources are different over time, and such changes will affect the performance of the tasks running on the grid.
- This implies that it would take amount of computation time to obtain an optimal solution, especially for a large-scale scheduling problem.
- Gambardella, 1997] and particle swarm optimization [Kennedy &.
- Strogatz, 1998], project scheduling [Chen, 2010], call center scheduling [chiu et al., 2009], and others [Behnamian et al., 2010.
- Hei et al., 2009]..
- The particle swarm optimization (PSO) is a swarm intelligent inspired scheme which was first proposed by Kennedy and Eberhart [Kennedy &.
- However, many PSO derivatives have been studied, and one of them was named “discrete” particle swarm optimization (DPSO) algorithm proposed by Kennedy et al.
- representing how DPSO can be used to solve problems.
- Hence, this study focuses on applying discrete particle swarm optimization algorithm to solve the task scheduling problem in grid computing..
- To enhance the performance of the applied DPSO, additional heuristic was introduced to solve the investigated scheduling problem in grid.
- The task scheduling problem in grid computing.
- This section gives a class of task scheduling problem in homogeneous grid.
- The introduced grid task scheduling problem can be represented as a task interaction graph (TIG) proposed by Salman et.al.
- Grid task scheduling problem representation [Salman et al., 2002].
- A meta-heuristic algorithm that is based on the principles of discrete particle swarm optimization (PSO) is proposed for solving the grid scheduling problem.
- M} is the set of the tasks and E are the interactions between these tasks as in Fig.
- The p i is the processing time (cost) corresponding to the work load to be performed by task i on grid.
- The grid system can be represented as a grid environment graph (GEG) G (P, C), where P = {1, 2.
- N} is the set of grids in the distributed system.
- The problem can be defined as:.
- A k is the set of tasks assigned to grid k (2) C mem (k).
- A k is the set of tasks assigned to grid k (3) C com (k).
- Where C exe (k) is the total execution time of all tasks assigned to grid k and C com (k) is the total communication cost between tasks assigned to grid k.
- The objective of the task assignment problem is to find an assignment schedule that the cost is minimized of one grid for a given TIG on a given GEG.
- Particle swarm optimization.
- The particles swarm optimization (PSO) was first proposed by Kennedy and Eberhart in 1995..
- There are a lot of task-resource assignment related works have been introduced in recent years [Kuo et al.
- However, the combinatorial problems are most of discrete or quantitative variables [Liao et al., 2007].PSO schematic diagram is displayed as in Fig.
- The introduced grid task scheduling problem as in Fig.
- 1 can be regarded as a task-grid assignment problem in a graph as in Fig.
- The particle swarm optimization is a multi-agent general meta-heuristic method, and can be applied extensively in solving many NP-complete or combinatorial problems.
- the position of a particle is indicated by a vector which presents a potential solution of the problem.
- In every generation or iteration, the local bests and global best are determined through evaluating the performances, i.e., the fitness values of current population of particles.
- one is the global experience position of all particles, which memorizes the global best solution obtained from all positions (solutions) of all particles.
- the other is the individual experience position of each particle, which memorizes the local best solution acquired from the positions (solutions) of the corresponding particle has been at..
- These two experience positions and the inertia weight of the previous velocities used to determine the impact on the current velocity.
- The velocity retains part of prior velocity (the inertia) and driving particle toward the direction based on the global experience position and the individual experience position.
- X ij is the j th component of the i th position.
- where V ij is the velocity component corresponding to the component of X ij , and the individual experience is a position L i = {L i1.
- L iM } which is the local best solution for the i th particle.
- The mentioned parameters above are used to calculate the updating of the j th component of the position and velocity for the i th particle, as shown in Eq.
- Where w is an inertia weight used to determine the influence of the previous velocity to the new velocity.
- SA is one of the popular algorithms to be combined with other meta-heuristic schemes.
- Simulated annealing (SA) was first introduced by Metropolis in 1953 [Metropolis et al., 1953].
- Furthermore, SA is one of the efficient methods applied to solve widely complex problems [Kirkpatrick, 1983].
- The temperature, T, is the magnitude of fluctuation.
- The acceptance criterion of worse solution is based on the probabilistic process which is dependent on the temperature and energy difference between two states.
- Discrete particle swarm optimization method.
- Firstly, the particle is composed of the binary variable.
- Secondly, the velocity represents the probability of the binary variable taking the value of one, i.e., the probability of task i is assigned to grid k in this study (i∈ {1, 2.
- The discrete PSO is adopted by generating solutions for updating the particle’s position and velocity vectors to solve the task scheduling problem in parallel machines [Kashan &.
- Kashan et al., 2008.
- Lee et al., 2006].
- Another similar to the discrete PSO optimization technique developed by Laskari et al.
- [Laskari et al., 2002], which is based on the truncation of the real values to their nearest integer.
- This study conducts the discrete PSO method introduced by [Liao et al., 2007] and combines the SA algorithm for solving the task assignment problems in grid.
- For the h th particle (h =1.
- X hij ∈{0,1}is the i th task assigned to grid j for particle h ( i =1.
- where V hij is the velocity associated with component X hij , and the individual experience for particle h is L h = {L h11.
- Above stated parameters are then used to update all components of the V h .
- Equation (9) is the sigmoid function as displayed in Fig.
- Therefore, in the proposed algorithm, each particle h places the unscheduled task i to grid j according to the following normalized probability [Liao et al., 2007]:.
- U is the set of grids (11).
- Restated, the determination of which grid to be assigned to an unscheduled task in the study is based on the roulette wheel selection rule which is well applied in genetic algorithm.
- Hence, according to roulette wheel selection rile, grid j is randomly selected from U for task i based on the probability distribution given by Eq.
- Based on the pseudo code of discrete PSO given by Kennedy et al.
- The computation steps of the proposed algorithm in the simulation system can be summarized as:.
- objective function g = h //g is the index of the global best G End if.
- Update the velocity matrix Vh based on Eq.
- map Vhij to s(Vhij) based on Eq.
- Lh is the best so far for particle h End if.
- Hence, the normalized probability q h (i, j) (based on Eq.
- Finally, task-grid assignment based on roulette wheel selection rule will be.
- To verify the performance of the presented algorithm (SA + discrete PSO), some simulation cases will be tested.
- Simulations use the cases of 5 and 10 tasks in 4 grids and 5 grids respectively to verify the performance of the proposed algorithm.
- In the example of 5-task in 4 grids environment, the best solution can be found in Table 9..
- Based on Tables 3 and 4, task 4 has interaction with tasks 1 and 3, and the communication cost to tasks 1 and 3 is .
- Thus, the total cost for grid 4 is 48.
- Restated, more complicated scheduling problem can be further solved using discrete PSO.
- Further research encourages that the extension of the discrete PSO by incorporating other meta-heuristics for solving different scheduling problems is recommended..
- Combining competitive scheme with slack neurons to solve real-time job scheduling problem.
- Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB..
- The Anatomy of the Grid: Enabling Scalable Virtual Organizations.
- Novel scheduling strategy for downlink multiuser MIMO system: Particle swarm optimization.
- A discrete particle swarm optimization algorithm for scheduling parallel machines.
- A discrete binary version of the particle swarm algorithm.
- An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model.
- Particle swarm optimization for integer programming.
- Proceedings of the IEEE Congress on Evolutionary Computation, pp.
- A discrete version of particle swarm optimization for flowshop scheduling problems.
- Particle swarm optimization for task assignment problem.
- A hybrid particle swarm optimization for job shop scheduling problem