A Memetic Gravitation Search Algorithm for Solving Permutation Flow Shop Scheduling

Abstract:

The permutation flow-shop scheduling problem (PFSP) is an non-deterministic polynomialtime (NP) hard combinatorial optimization problems and has been widely researched within thescheduling community. In this paper, a memetic gravitation search algorithm (MGSA) is proposedto solve the PFSP for minimizing the makespan measure. The smallest position value (SPV) rule isutilized for converting the continuous number to job permutations for determining the most suitablethe proposed MGSA for the PFSP. The proposed MGSA uses a Nawaz-Enscore-Ham (NEH) heuristicalgorithm for initialization of population, and a simulated annealing (SA) is coupled with the variableneighborhood search (VNS) as the local search method to balance exploitation and exploration. Toverify the robustness of the MGSA, it is compared with three particle swarm optimization (PSO) algorithmson the basis of 12 PFSP instances with different job sizes ranging from 20 to 500. The resultsdemonstrate that the proposed MGSA can outperform other compared algorithms.

• Periodical: Advanced Materials Research (Volumes 1079-1080)
• Pages: 626-630
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1079-1080.626
• Online since: December 2014
• Authors: Ko Wei Huang*, Jui Le Chen, Chu Sing Yang
• Keywords: Gravitation Searching Algorithm, Makespan, NEH Heuristic, Permutation Flow Shop Scheduling Problem, Smallest Position Value

References

[1] O. Etiler, B. Toklu, M. Atak, and J. Wilson., A genetic algorithm for flow shop scheduling prob- lems, The Journal of the Operational Research Society, 55 (2004), p.830--835.

DOI: 10.1057/palgrave.jors.2601766

[2] Michel Gendreau and Jean-Yves Potvin, Handbook of Metaheuristics, Springer Publishing Com- pany, Incorporated, 2nd ed., (2010).

[3] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), p.671--680.

DOI: 10.1126/science.220.4598.671

[4] Bo Liu, Ling Wang, and Yi-Hui Jin, An effective pso-based memetic algorithm for flow shop scheduling, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 37 (2007), p.18 --27.

DOI: 10.1109/tsmcb.2006.883272

[5] C. Low, J. Yeh, and K. Huang., A robust simulated annealing heuristic for flow shop scheduling problem, International Journal of Advanced Manufacturing Technology, 23 (2004), p.762--767.

DOI: 10.1007/s00170-003-1687-x

[6] M. Nawaz, E Emory Enscore Jr, and I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA, 11 (1983), p.91--95.

DOI: 10.1016/0305-0483(83)90088-9

[7] C. Rajendran and H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to min- imize makespan/total flowtime of jobs, European Journal of Operational Research, 155 (2004), p.426--438.

DOI: 10.1016/s0377-2217(02)00908-6

[8] K. Rameshkumar, R. Suresh, and K. Mohanasundaram, Discrete particle swarm optimization (dpso) algorithm for permutation flowshop scheduling to minimize makespan, in Advances in Natural Computation, vol. 3612 of Lecture Notes in Computer Science, Springer Berlin / Hei- delberg, 2005, p.572.

DOI: 10.1007/11539902_70

[9] Esmat Rashedi, Hossein Nezamabadi-pour, and Saeid Saryazdi, GSA: A gravitational search algorithm, Information Sciences, 179 (2009), p.2232 -- 2248.

DOI: 10.1016/j.ins.2009.03.004

[10] E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Re- search, 64 (1993), p.278--285.

DOI: 10.1016/0377-2217(93)90182-m

[11] M. Fatih Tasgetiren, Yun-Chia Liang, Mehmet Sevkli, and Gunes Gencyilmaz, A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flow- shop sequencing problem, European Journal of Operational Research, 177 (2007).

DOI: 10.1016/j.ejor.2005.12.024

[12] J. P. Watson, L. Barbulescu, L. D. Whitley, and A. E. Howe, Contrasting structured and ran- dom permutation flow-shop scheduling problems: Search-space topology and algorithm perfor- mance, ORSA Journal on Computing, 14 (2002), p.98--123.

DOI: 10.1287/ijoc.14.2.98.120

[13] Ko wei Huang, Chu sing Yang, and Chun wei Tsai, A two-phase hybrid particle swarm optimiza- tion algorithm for solving permutation flow-shop scheduling problem, International Journal of Computer Applications, 48 (2012), p.11--18.

DOI: 10.5120/7311-9883

[14] Zhanpeng Xie, Chaoyong Zhang, Xinyu Shao, Wenwen Lin, and Haiping Zhu, An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem, Advances in Engineering Software, 77 (2014), p.35 -- 47.

DOI: 10.1016/j.advengsoft.2014.07.006