Cellular particle swarm optimization with a simple adaptive local search strategy for the permutation flow shop scheduling problem

• Autorzy: Seck-Tuoh-Mora Juan C. , Medina-Marin Joselito , Martinez-Gomez Erick S. , Hernandez-Gress Eva S. , Hernandez-Romero Norberto , Volpi-Leon Valeria

Identyfikatory

DOI

10.24425/acs.2019.129378

• Języki publikacji: EN

Abstrakty

EN

Permutation flow shop scheduling problem deals with the production planning of a number of jobs processed by a set of machines in the same order. Several metaheuristics have been proposed for minimizing the makespan of this problem. Taking as basis the previous Alternate Two-Phase PSO (ATPPSO) method and the neighborhood concepts of the Cellular PSO algorithm proposed for continuous problems, this paper proposes the improvement of ATPPSO with a simple adaptive local search strategy (called CAPSO-SALS) to enhance its performance. CAPSO-SALS keeps the simplicity of ATPPSO and boosts the local search based on a neighborhood for every solution. Neighbors are produced by interchanges or insertions of jobs which are selected by a linear roulette scheme depending of the makespan of the best personal positions. The performance of CAPSO-SALS is evaluated using the 12 different sets of Taillard’s benchmark problems and then is contrasted with the original and another previous enhancement of the ATPPSO algorithm. Finally, CAPSO-SALS is compared as well with other ten classic and state-of-art metaheuristics, obtaining satisfactory results.

Słowa kluczowe

EN

flow shop; particle swarm optimization (PSO); local search strategy; hybrid search method; cellular automata; scheduling

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2019
• Tom: Vol. 29, No. 2
• Strony: 205--226
• Opis fizyczny: Bibliogr. 35 poz., rys., tab., wzory

Twórcy

autor

Seck-Tuoh-Mora Juan C.

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

autor

Medina-Marin Joselito

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

autor

Martinez-Gomez Erick S.

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

autor

Hernandez-Gress Eva S.

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

autor

Hernandez-Romero Norberto

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

autor

Volpi-Leon Valeria

• Engineering Department, Autonomous University of Hidalgo State, Carr. Pachuca-Tulancingo, Col. Carboneras, Mineral de la Reforma, Hidalgo 42184, Mexico

Bibliografia

• [1] A. Banks, J. Vincent, and C. Anyakoha: A review of particle swarm optimization. Part II: Hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Natural Computing, 7(1), (2008) 109–124.
• [2] M. Bessedik, F. B. S. Tayeb, H. Cheurfi, and A. Blizak: An immunity-based hybrid genetic algorithms for permutation flowshop scheduling problems. The International Journal of Advanced Manufacturing Technology, 85(9-12), (2016), 2459–2469.
• [3] A. W. Burks: Essays on cellular automata. University of Illinois Press, 1970.
• [4] P. C. Chang, S. H. Chen, C. Y. Fan, and V. Mani: Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems. Annals of Operations Research, 180(1), (2010), 197–211.
• [5] C. L. Chen, S. Y. Huang, Y. R. Tzeng, and C. L. Chen:Arevised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem. Soft Computing, 18(11), (2014), 2271–2282.
• [6] S. H. Chen, P.C. Chang, T. Cheng, and Q. Zhang: A self-guided genetic algorithm for permutation flowshop scheduling problems. Computers & Operations Research, 39(7), (2012), 1450–1457.
• [7] X. Dong, M. Nowak, P. Chen, and Y. Lin: Self-adaptive perturbation and multi-neighborhood search for iterated local search on the permutation flow shop problem. Computers & Industrial Engineering, 87, 176–185 (2015)
• [8] K. L. Du and M. Swamy: Particle swarm optimization. In: Search and Optimization by Metaheuristics, pp. 153–173. Springer, 2016.
• [9] K. Fleszar and K. S. Hindi: An effective vns for the capacitated p-median problem. European Journal of Operational Research, 191(3), (2008), 612–622.
• [10] L. Gao, J. Huang, and X. Li: An effective cellular particle swarm optimization for parameters optimization of a multi-pass milling process. Applied Soft Computing, 12(11), (2012), 3490–3499. https://doi.org/10.1016/j.asoc.2012.06.007, http://www.sciencedirect.com/science/article/pii/S1568494612002785.
• [11] E. Garcia-Gonzalo and J. Fernandez-Martinez: A brief historical review of particle swarm optimization (pso). Journal of Bioinformatics and Intelligent Control, 1(1), (2012), 3–16.
• [12] S. Gholizadeh: Layout optimization of truss structures by hybridizing cellular automata and particle swarm optimization. Computers & Structures, 125 (2013), 86–99. http://dx.doi.org/10.1016/j.compstruc.2013.04.024. http://www.sciencedirect.com/science/article/pii/S0045794913001557
• [13] B. Jarboui, S. Ibrahim, P. Siarry, and A. Rebai: A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, 54(3), (2008), 526–538.
• [14] S. M. Johnson: Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics (NRL), 1(1), (1954), 61–68.
• [15] P. Lagos-Eulogio, J. C. Seck-Tuoh-Mora, N. Hernandez-Romero, and J. Medina-Marin:Anewdesign method for adaptive iir system identification using hybrid cpso and de. Nonlinear Dynamics, 88(4), (2017), 2371–2389.
• [16] S. Lalwani, R. Kumar, and N. Gupta: A review on particle swarm optimization variants and their applications to multiple sequence alignment. Journal of Applied Mathematics and Bioinformatics, 3(2), (2013), 87.
• [17] C. J. Liao, C. T. Tseng, and P. Luarn: A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34(10), (2007), 3099–3111.
• [18] R. Liu, C. Ma, W. Ma, and Y. Li: A multipopulation pso based memetic algorithm for permutation flowshop scheduling. The ScientificWorld Journal, 2013 (2013).
• [19] Y. Marinakis and M. Marinaki: Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem. Soft Computing, 17(7), (2013), 1159–1173.
• [20] H. V. McIntosh: One Dimensional Cellular Automata. Luniver Press, 2009.
• [21] T. Morton and D. W. Pentico: Heuristic scheduling systems: with applications to production systems and project management, vol. 3. John Wiley & Sons, 1993.
• [22] Q. K. Pan and R. Ruiz: Local search methods for the flowshop scheduling problem with flowtime minimization. European Journal of Operational Research, 222(1), (2012), 31–43.
• [23] Q. K. Pan, M. F. Tasgetiren, and Y. C. Liang: A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 55(4), (2008), 795–816.
• [24] Q. K. Pan, M. F. Tasgetiren, and Y. C. Liang: A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers & Operations Research, 35(9), (2008), 2807–2839.
• [25] Q. K. Pan, L. Wang, M. F. Tasgetiren, and B. H. Zhao: A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion. The International Journal of Advanced Manufacturing Technology, 38(3–4), (2008), 337–347.
• [26] M. L. Pinedo: Scheduling: theory, algorithms, and systems. Springer, 2016.
• [27] C. R. Reeves: A genetic algorithm for flowshop sequencing. Computers & Operations Research, 22(1), (1995), 5–13.
• [28] Y. Shi, H. Liu, L. Gao, and G. Zhang: Cellular particle swarm optimization. Information Sciences, 181(20), (2011), 4460–4493, Special Issue on Interpretable Fuzzy Systems, http://dx.doi.org/10.1016/j.ins.2010.05.025. http://www.sciencedirect.com/science/article/pii/S0020025510002288.
• [29] E. Taillard: Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), (1993), 278–285.
• [30] L. Tang and J. Liu: A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time. Journal of Intelligent Manufacturing, 13(1), (2002), 61–67.
• [31] M. F. Tasgetiren, Y. C. Liang, M. Sevkli, and G. Gencyilmaz: A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), (2007), 1930–1947.
• [32] K. C. Ying and C. J. Liao: An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31(5), (2004), 791–801.
• [33] M. Yu, Y. Zhang, K. Chen, and D. Zhang: Integration of process planning and scheduling using a hybrid ga/pso algorithm. The International Journal of Advanced Manufacturing Technology, 78(1–4), (2015), 583–592.
• [34] C. Zhang, J. Ning, and D. Ouyang: A hybrid alternate two phases particle swarmoptimization algorithm for flowshop scheduling problem. Computers & Industrial Engineering, 58(1), (2010), 1–11.
• [35] G. Zobolas, C. D. Tarantilis, and G. Ioannou: Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36(4), (2009), 1249–1267

Uwagi

EN

1. This work was partially supported by National Council for Science and Technology (CONACYT) with project number CB-2014-237323.

PL

2. Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).