ISSN ONLINE(2319-8753)PRINT(2347-6710)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Minimization of Total Weighted Delay in Flowshop Sequencing Problem Using Particle Swarm Optimization

S.V.R.Arun1, S.Porselvi2, DR.A.N.Balaji3
  1. ME (CAD/CAM), K.L.N college of Engineering, Tamilnadu, india
  2. Assitant professor, Department of mechanical engg, K.L.N college of Engineering, Tamilnadu, india
  3. professor, Department of mechanical engg, K.L.N college of Engineering, Tamilnadu, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

Scheduling problems have played a vital role in recent years due to the fast growing of consumer demand for variety,quality, reduced product life cycles, competing with global competition and rapid development of new technologies. The Flow Shop Scheduling Problem (FSP) is one of the most popular scheduling models existing in practice, which is among the hardest combinatorial optimization problems . Particle Swarm Optimization (PSO) is a population based metaheuristic that takes advantage of indvidual and social cooperation in a Swarm. It has been applied to variety of optimization problems because of its simplicity and fast convergence. In this paper PSO is presented to solve the flowshop sequencing problem with an objective of minimizing the Total weighted delay of jobs. For this purpose a heuristic rule called the smallest position value(SPV) is used to enable the continous PSO to be applied in sequencing problems.

Keywords

Particle Swarm Optimization , Shortest position value rule, Total weighted delay

INTRODUCTION

Metaheuristics are general frameworks commonly used for solving hard optimization problems. To examine a search space systematically, they employ intelligent and powerful heuristic mechanisms for both exploration and exploitation ([2] Mostafa Akhshabi, Javad Haddadnia). Amongst several metaheuristics using various search philosophies, ones providing dynamic balance between exploration and exploitation, usually deliver better performance. If exploration is the governing feature of a metaheuristic, it may perform a vague examination on the search space and generally misses good solutions. On the contrary, if exploitation is dominant, the entire search space may not be explored and premature convergence to a local optimum is possible Particle Swarm Optimization (PSO) is a metaheuristic introduced by Kennedy and Eberhart .
PSO is inspired of the behaviors of social models like bird flocking or fish schooling and is based on individual improvement and social cooperation [J. Jerald · P. Asokan [4]]. In PSO, a population of particles (swarm) flies over a multidimensional search space representing candidate solutions. During their search journey determined by their current tendency, personal experience and swarm’s experience, particles are expected to explore the whole search space and to tend towards the optimal solution PSO is initially proposed for continuous nonlinear optimization problems ([8] Ken Van den Enden2 and Thomas St¨utzle). Later it becomes quite popular and is applied to a wide range of optimization problems due to rapid swarm convergence and simplicity in its conceptual features and implementation . Although rapid convergence is a desirable advantage, it may result in a severe premature convergence problem, as well . The swarm may converge to a local solution and may not escape from it to explore the search space thoroughly. Moreover, PSO has a shortcoming in finding the best solution around a local neighborhood . Several modifications on the standard PSO algorithm are proposed to rectify above mentioned drawbacks. Most of these modifications concern only on either exploration or exploitation mechanism and merely correct the deficiencies partially. They locate good solutions for some of the problem types but fail to produce competitive results for others. For instance, while the methods concentrated on exploration mechanism improve the solution quality for multimodal continuous function optimization problems, they typically generate inferior solutions for unimodal problems. In this paper, a PSO algorithm with improved exploration and exploitation mechanisms is proposed. In PSO, the general flow of the PSO algorithm is preserved. However, among the PSO iterations, the search strategy is temporarily modified only for the particle(thepioneering-particle) which achieves or enhances the best solution. For the pioneering-particles, Shortest position value(SPV) is employed. The solutions obtained by SPV do not affect swarm’s experience in order to find promising search areas afterwards and not to hinder exploration. To improve exploration further and to prevent premature convergence, the pioneering-particles continue their search journey with random velocities and their previous experience. The primary advantage of PSO is its applicability to many different types of optimization problems with satisfactory performance. To support this claim, we experimented PSO on both continuous and discrete problems. Results for the continuous problems indicate that our approach improves the search capability of the standard PSO algorithm. PSO produces comparable solutions for both unimodal and multimodal functions while other similar PSO variants deliver poor solutions for either unimodal or multimodal functions. Moreover, our approach achieves the best known solutions for almost all instances of the Orienteering Problem (OP) which is a discrete NP-hard problem.Besides proposing a promising and valuable tool for solving different types of problems (continuous or discrete / unimodal or multimodal) satisfactorily, there are two auxiliary contributions of this paper; Firstly,we present the first successful PSO based algorithm for OP . IS-PSO which is derived from PSO,reproduces the best known solutions for all benchmark problems. Secondly, we propose that SPV with dynamic neighborhoods is a good alternative for a subsidiary local search([5] M.Faith Tasgetiren et al).

PARTICLE SWARM OPTIMIZATION

Particle Swarm Optimization (PSO) is a population-based method in which a swarm includes n individuals called particles. Each particle has a d-dimensional position vector representing a candidate solution and a ddimensional velocity vector expressing the current tendency of the particle during its search journey. Initial swarm can be constructed randomly or by using some predetermined values. At each step, the velocity of each particle is re-evaluated based on the particle’s inertia as well as the social interaction (swarm’s experience) and personal experience of the particle. The experience of each particle is usually captured by its local best position(pbest ). The experience of the swarm is captured by the global best position (gbest ). In the course of several iterations, particles make use of this experience and are supposed to move towards the optimum position.
PSEUDO CODE
Procedure of PSO
Initialize parameters
Initialize population
For each particle
Evaluate
Update Local best
Update global best
Update velocity and position
While(not terminated)
End procedure
Pseudo-code of the standard PSO algorithm is illustrated above. Optimization is achieved in the course of several iterations of update-evaluate steps. During the update step at iteration t, the velocity and the position vector of each particle are calculated by using equations . In these equations are the velocity and the position values of the jth dimension (1 ≤ j ≤ d) of the ith particle (1 ≤ i ≤ n) at iteration . The stochastic behavior of PSO is achieved by random numbers rand 1 and rand 2 which are positive numbers generally uniformly distributedin [0, 1].
After the update step, the fitness function value is calculated for each particle based on its position (the candidate solution represented by the particle.) The local best position, pbest of each particle and the global best position, gbest of the swarm are updated if the candidate solution is better than gbest is considered as the best solution.PSO algorithm for FSP The gbest model of kennedy et al.is followed in this study.according to the gbest model,each particle moves towards its best previous position and towards the best particle moves towards the best particle in the whole swarm.In the PSO alogorithm for fsp,parameters were initialized and the initial population was generated randomly since evaluation of each particle in the swarm requires the determination of the permutations of the job for fsp, the smallest position value(SPV) rule applies to each particle corresponding permutation thus each particle will be evaluated by using the permutation to compute the fitness function value.the objective function for the fsp with total weighted delay.after evaluation ,the PSO algorithm repeats the following steps iteratively. With its position,velocity,and fitness value,each particle updates its personal best (best value of each individual so far) if an improved fitness value was found.on the other hand the best particle in the whole swarm with its fitness and position was used to update the global best. Then the velocity of the particle is updated by using its previous velocity,the experiences of the personal best,and global best in order to determine the position of each particle. The permutation is determined through the SPV rule so that evaluation is again performed to compute the fitness of the particles in the swarm .this process is terminated with a pre-determined stopping criterion.
image
image'
image
The personsal best delay got is in sequence 3-2-4-5- 1=250

CONCLUSION

To the best of my knowledge ,this is the first reported application of the particle swarm optimization algorithm to solve the FSP with total weighted delay of jobs in the literature. Here SPV rule is used to enable the continuous PSO algorithm to be applied to all classes of sequencing problems.and the result got is better than the global best solution

References

  1. Alebachew D. Yimer, Kudret Demirli (Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines) International Journal of Approximate Reasoning 50 (2009) 117–137
  2. Rasaratnam Logendran_, Paula deSzoeke, Faith Barnard (equence-dependent group scheduling problems in flexible flow shops) Int. J. Production Economics 102 (2006) 66–86
  3. Ruben Ruiz a,*, Jose Antonio Vazquez-Rodriguez The hybrid flow shop scheduling problem
  4. J. Jerald · P. Asokan · G. Prabaharan · R. Saravanan Scheduling optimisation of flexible manufacturing systems using particle swarm optimisation algorithm
  5. M.Faith Tasgetiren,yun-chia liang (A particle swarm optimization algorithm for makespan and flowtime minimization in the permutation flowshops sequencing problem) european journal of operational research 177(2007)1930-1947
  6. Bo Liua,b,c,∗, Ling Wanga, Ying Liud, Bin Qiane, Yi-Hui Jin (An effective hybrid particle swarm optimization for batch scheduling of polypropylene processes)
  7. Junqi Zhang Kun Liu Ying Tan∗ Xingui He (Allocation of Local and Global Search Capabilities of Particle in Canonical PSO)
  8. A. Montes de Oca1, Ken Van den Enden2 and Thomas St¨utzle (Incremental Particle Swarm-Guided Local Search for Continuous Optimization.)
  9. Suk-Hun Yoon, Jose A. Ventura, (Minimizing the mean weighted absolute deviation from due dates in lot-streaming flow shop scheduling), Computers & Operations Research ,29, (2002) 1301-1315
  10. Buthainah F Al-Dulaimi and Hamza A.Ali, (A Novel Genetic Algorithm Approach for Solving Flow Shop Problem), IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.9, September 2008.
  11. Mostafa Akhshabi, Javad Haddadnia, Mohammad Akhshabi, (Solving flow shop scheduling problem using a parallel genetic Algorithm), Procedia Technology 1 ( 2012 ) 351 – 355.
  12. Pempera Jarosław, Smutnicki Czesław, ˙ Zelazny Dominik, (Optimizing bicriteria flow shop scheduling problem bysimulated annealing algorithm), Procedia Computer Science 18 ( 2013 ) 936 – 945.
  13. F. Jolai, H. Asefi, M. Rabiee, P. Ramezani , (Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem) Scientia Iranica E (2013) 20 (3), 861–87