CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

A Two-Phase Hybrid Particle Swarm Optimization Algorithm for Solving Permutation Flow-Shop Scheduling Problem

by Ko-wei Huang, Chu-sing Yang, Chun-wei Tsai
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 48 - Number 1
Year of Publication: 2012
Authors: Ko-wei Huang, Chu-sing Yang, Chun-wei Tsai
10.5120/7311-9883

Ko-wei Huang, Chu-sing Yang, Chun-wei Tsai . A Two-Phase Hybrid Particle Swarm Optimization Algorithm for Solving Permutation Flow-Shop Scheduling Problem. International Journal of Computer Applications. 48, 1 ( June 2012), 11-18. DOI=10.5120/7311-9883

@article{ 10.5120/7311-9883,
author = { Ko-wei Huang, Chu-sing Yang, Chun-wei Tsai },
title = { A Two-Phase Hybrid Particle Swarm Optimization Algorithm for Solving Permutation Flow-Shop Scheduling Problem },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 48 },
number = { 1 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 11-18 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume48/number1/7311-9883/ },
doi = { 10.5120/7311-9883 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:42:57.873896+05:30
%A Ko-wei Huang
%A Chu-sing Yang
%A Chun-wei Tsai
%T A Two-Phase Hybrid Particle Swarm Optimization Algorithm for Solving Permutation Flow-Shop Scheduling Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 48
%N 1
%P 11-18
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, a two-phase hybrid particle swarm optimization algorithm (PRHPSO) is proposed for the permutation flow-shop scheduling problem (PFSP) with the minimizing makespan measure. The smallest position value (SPV) rule is used for encoding the particles that enable PSO for suitable PFSP, and the NEH and Tabu search algorithms are used for initializing the particles. In the first phase, the pattern reduction (PR) operator is used in the PSO algorithm for reducing the computation time. In order to avoid a premature convergence, a regeneration operator is used for escaping to the local optimal and balancing exploitation and exploration in the second phase. Additionally, a simulated annealing (SA) algorithm is utilized for local search to improve the best solution after the PSO search process. Finally, the results show that PRHPSO is significantly faster than two PSO-based algorithms and presents large-sized benchmarks.

References
  1. S. M. Johnson, "Optimal two- and three-stage production schedules withsetup times included," Naval Research Logistics Quarterly, vol. 1, pp. 61–68, 1954.
  2. A. H. G. Rinnooy Kan, Machine scheduling problems: Classification,complexity and computations. Martinus Nijhoff, The Hague, 1976.
  3. M. R. Garey, D. S. Johnson, and R. Sethi, "The complexity of flowshopand jobshop scheduling," Mathematics of Operations Research, vol. 1,pp. 117–129, 1976.
  4. M. Nawaz, E. E. Enscore Jr, and I. Ham, "A heuristic algorithm for them-machine, n-job flow-shop sequencing problem," OMEGA, vol. 11,no. 1, pp. 91–95, 1983.
  5. I. H. Osman and C. N. Potts, "Simulated annealing for permutationflow-shop scheduling," Omega, vol. 17, no. 6, pp. 551–557, 1989.
  6. C. Low, J. Yeh, and K. Huang. , "A robust simulated annealing heuristicfor flow shop scheduling problem," International Journal of AdvancedManufacturing Technology, vol. 23, pp. 762–767, 2004.
  7. E. Nowicki and C. Smutnicki, "A fast tabu search algorithm for thepermutation flow-shop problem," European Journal of OperationalResearch, vol. 91, no. 1, pp. 160–175, 1996.
  8. J. P. Watson, L. Barbulescu, L. D. Whitley, and A. E. Howe, "Contrastingstructured and random permutation flow-shop scheduling problems:Search-space topology and algorithm performance," ORSA Journal onComputing, vol. 14, pp. 98–123, 2002.
  9. C. R. Reeves, "A genetic algorithm for flowshop sequencing," Computersand Operations Research. , vol. 22, pp. 5–13, January 1995.
  10. O. Etiler, B. Toklu, M. Atak, and J. Wilson. , "A genetic algorithmfor flow shop scheduling problems," The Journal of the OperationalResearch Society, vol. 55, no. 8, pp. 830–835, 2004.
  11. T. St¨utzle, F. Intellektik, F. Informatik, and T. H. Darmstadt, "Anant approach to the flow shop problem," in In Proceedings of the6th European Congress on Intelligent Techniques & Soft Computing(EUFIT'98, 1997, pp. 1560–1564.
  12. C. Rajendran and H. Ziegler, "Ant-colony algorithms for permutationflowshop scheduling to minimize makespan/total flowtime of jobs,"European Journal of Operational Research, vol. 155, no. 2, pp. 426–438,2004. .
  13. Q. -K. Pan, M. F. Tasgetiren, and Y. -C. Liang, "A discrete differentialevolution algorithm for the permutation flowshop scheduling problem,"Computers and Industrial Engineering, vol. 55, no. 4, pp. 795–816,2008.
  14. Q. -K. Pan, L. Wang, and B. Qian, "A novel differential evolution algorithmfor bi-criteria no-wait flow shop scheduling problems," Computersand Operations Research, vol. 36, pp. 2498–2511, 2009.
  15. B. Qian, L. Wang, R. Hu, W. -L. Wang, D. -X. Huang, and X. Wang, "Ahybrid differential evolution method for permutation flow-shop scheduling,"The International Journal of Advanced Manufacturing Technology,vol. 38, pp. 757–777, 2008.
  16. Y. Zhang, X. Li, and Q. Wang, "Hybrid genetic algorithm for permutationflowshop scheduling problems with total flowtime minimization,"European Journal of Operational Research, vol. 196, no. 3, pp. 869–876,2009.
  17. T. -C. Chiang, H. -C. Cheng, and L. -C. Fu, "NNMA: An effective memeticalgorithm for solving multiobjective permutation flow shop schedulingproblems," Expert Systems with Applications, vol. 38, no. 5, pp. 5986 –5999, 2011. .
  18. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization bysimulated annealing," Science, vol. 220, pp. 671–680, 1983.
  19. N. Mladenovic, "Variable neighborhood search," Computers and OperationsResearch, vol. 24, no. 11, pp. 1097–1100, 1997.
  20. E. Taillard, "Some efficient heuristic methods for the flow shop sequencingproblem," European Journal of Operational Research, vol. 47, no. 1,pp. 65–74, Jul. 1990.
  21. T. Aldowaisan and A. Allahverdi, "New heuristics for no-wait flowshopsto minimize makespan," Computers and Operations Research, vol. 30,no. 8, pp. 1219 – 1231, 2003.
  22. P. J. Kalczynski and J. Kamburowski, "An improved neh heuristicto minimize makespan in permutation flow shops," Computers andOperations Research, vol. 35, pp. 3001–3008, 2008.
  23. F. Glover and M. Laguna, Tabu Search. Norwell, MA, USA: KluwerAcademic Publishers, 1997.
  24. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, andE. Teller, "Equation of State Calculations by Fast Computing Machines,"The Journal of Chemical Physics, vol. 21, no. 6, pp. 1087–1092, 1953.
  25. J. Kennedy and R. Eberhart, "Particle swarm optimization," in NeuralNetworks, 1995. Proceedings. , IEEE International Conference on, vol. 4,1995, pp. 1942–1948.
  26. J. Kennedy and R. C. Eberhart, "A discrete binary version of the particleswarm algorithm," in IEEE International Conference on Systems, Man,and Cybernetics,, vol. 5, 1997, pp. 4104–4108.
  27. M. Tasgetiren, M. Sevkli, Y. -C. Liang, and G. Gencyilmaz, "Particleswarm optimization algorithm for permutation flowshop sequencingproblem," in Ant Colony Optimization and Swarm Intelligence. SpringerBerlin / Heidelberg, 2004.
  28. K. Rameshkumar, R. Suresh, and K. Mohanasundaram, "Discrete particleswarm optimization (dpso) algorithm for permutation flowshopscheduling to minimize makespan," in Advances in Natural Computation,ser. Lecture Notes in Computer Science. Springer Berlin /Heidelberg, 2005, vol. 3612, p. 572581.
  29. Z. Lian, X. Gu, and B. Jiao, "A similar particle swarm optimizationalgorithm for permutation flowshop scheduling to minimize makespan,"Applied Mathematics and Computation, vol. 175, pp. 773–785, 2006.
  30. C. -J. Liao, C. -T. Tseng, and P. Luarn, "A discrete version of particleswarm optimization for flowshop scheduling problems," Computers andOperations Research, vol. 34, pp. 3099–3111, 2007.
  31. B. Liu, L. Wang, and Y. -H. Jin, "An effective pso-based memeticalgorithm for flow shop scheduling," Systems, Man, and Cybernetics,Part B: Cybernetics, IEEE Transactions on, vol. 37, no. 1, pp. 18 –27,feb. 2007.
  32. M. F. Tasgetiren, Y. -C. Liang, M. Sevkli, and G. Gencyilmaz, "A particleswarm optimization algorithm for makespan and total flowtime minimizationin the permutation flowshop sequencing problem," EuropeanJournal of Operational Research, vol. 177, no. 3, pp. 1930 – 1947, 2007.
  33. C. Zhang, J. Sun, X. Zhu, and Q. Yang, "An improved particle swarmoptimization algorithm for flowshop scheduling problem," InformationProcessing Letters, vol. 108, pp. 204–209, 2008.
  34. D. Sha and H. Hung Lin, "A particle swarm optimization for multiobjectiveflowshop scheduling," The International Journal of AdvancedManufacturing Technology, vol. 45, pp. 749–758, 2009.
  35. C. Zhang, J. Ning, and D. Ouyang, "A hybrid alternate two phases particleswarm optimization algorithm for flow shop scheduling problem,"Computers and Industrial Engineering, vol. 58, pp. 1–11, February 2010.
  36. H. Liu, L. Gao, and Q. Pan, "A hybrid particle swarm optimization withestimation of distribution algorithm for solving permutation flowshopscheduling problem," Expert Systems with Applications, vol. 38, pp. 4348–4360, 2011.
  37. Y. Shi and R. Eberhart, "A modified particle swarm optimizer," in Proceedingsof IEEE international conference on evolutionary computation,1998, pp. 69–73.
  38. J. C. Bean, "Genetic algorithms and random keys for sequencing andoptimization," ORSA Journal on Computing, vol. 6, no. 2, pp. 154–160,1994.
  39. M. -C. Chiang, C. -W. Tsai, and C. -S. Yang, "A time-efficient patterreduction algorithm for k-means clustering," Inf. Sci. , vol. 181, no. 4,pp. 716–731, Feb. 2011.
  40. I. M. Oliver, D. J. Smith, and J. R. C. Holland, "A study of permutationcrossover operators on the traveling salesman problem," in Proceedingsof the Second International Conference on Genetic Algorithms onGenetic algorithms and their application. Hillsdale, NJ, USA: L. Erlbaum Associates Inc. , 1987, pp. 224–230.
  41. E. Taillard, "Benchmarks for basic scheduling problems," EuropeanJournal of Operational Research, vol. 64, no. 2, pp. 278–285, January1993.
Index Terms

Computer Science
Information Sciences

Keywords

Particle Swarm Optimization Permutation Flow-shop Scheduling Problem Pattern Reduction Makespan Pattern Reduction Regeneration Operator

Powered by PhDFocusTM