Cover Image

The Discrete Particle Swarm Optimization Algorithms For Permutation Flowshop Scheduling Problem

Ikhlasul Amallynda


Abstract


In this paper, two types of discrete particle swarm optimization (DPSO) algorithms are presented to solve the Permutation Flow Shop Scheduling Problem (PFSP). We used criteria to minimize total earliness and total tardiness. The main contribution of this study is a new position update method is developed based on the discrete domain because PFSP is represented as discrete job permutations. In addition, this article also comes with a simple case study to ensure that both proposed algorithm can solve the problem well in the short computational time. The result of Hybrid Discrete Particle Swarm Optimization (HDPSO) has a better performance than the Modified Particle Swarm Optimization (MPSO). The HDPSO produced the optimal solution. However, it has a slightly longer computation time. Besides the population size and maximum iteration have any impact on the quality of solutions produced by HDPSO and MPSO algorithms 

Keywords


Flow shop; Earliness; Tardiness; Metaheuristic;Particle swarm optimization

Full Text:

PDF

References


[1] Y.-D. Kim, "Minimizing total tardiness in permutation flowshops," European Journal of Operational Research, vol. 85, pp. 541-555, 1995. https://doi.org/10.1016/0377-2217(94)00029-C.

[2] M. Avriel, M. Penn, and N. J. D. A. M. Shpirer, "Container ship stowage problem: complexity and connection to the coloring of circle graphs," vol. 103, pp. 271-279, 2000. https://doi.org/10.1016/S0166-218X(99)00245-0.

[3] V. A. Armentano and J. E. J. J. o. H. Claudio, "An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem," vol. 10, pp. 463-481, 2004. https://doi.org/10.1023/B:HEUR.0000045320.79875.e3.

[4] J.-S. Chen, J. C.-H. Pan, and C.-K. J. E. S. w. A. Wu, "Hybrid tabu search for re-entrant permutation flow-shop scheduling problem," vol. 34, pp. 1924-1930, 2008. https://doi.org/10.1016/j.eswa.2007.02.027.

[5] B. Ekşioğlu, S. D. Ekşioğlu, P. J. C. Jain, and I. Engineering, "A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods," vol. 54, pp. 1-11, 2008. https://doi.org/10.1016/j.cie.2007.04.004.

[6] F. S. Erenay, I. Sabuncuoglu, A. Toptal, and M. K. J. E. J. o. O. R. Tiwari, "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," vol. 201, pp. 89-98, 2010. https://doi.org/10.1016/j.ejor.2009.02.014.

[7] Y. Marinakis, M. J. C. Marinaki, and O. Research, "A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem," vol. 37, pp. 432-442, 2010. https://doi.org/10.1016/j.cor.2009.03.004.

[8] C.-W. Chiou, W.-M. Chen, C.-M. Liu, and M.-C. J. E. S. w. A. Wu, "A genetic algorithm for scheduling dual flow shops," vol. 39, pp. 1306-1314, 2012. https://doi.org/10.1016/j.eswa.2011.08.008.

[9] W.-H. Wu, W.-H. Wu, J.-C. Chen, W.-C. Lin, J. Wu, and C.-C. J. J. o. M. S. Wu, "A heuristic-based genetic algorithm for the two-machine flowshop scheduling with learning consideration," vol. 35, pp. 223-233, 2015. https://doi.org/10.1016/j.jmsy.2015.02.002.

[10] N. Karimi, H. J. C. Davoudpour, and O. Research, "A high performing metaheuristic for multi-objective flowshop scheduling problem," vol. 52, pp. 149-156, 2014. https://doi.org/10.1016/j.cor.2014.01.006.

[11] H. F. Rahman, R. Sarker, and D. J. A. E. Essam, "A genetic algorithm for permutation flowshop scheduling under practical make-to-order production system," vol. 31, pp. 87-103, 2017. https://doi.org/10.1017/S0890060416000196.

[12] S. A. Basir, M. M. Mazdeh, M. J. C. Namakshenas, and I. Engineering, "Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system," vol. 126, pp. 217-231, 2018. https://doi.org/10.1016/j.cie.2018.09.035.

[13] C. Yu, Q. Semeraro, A. J. C. Matta, and O. Research, "A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility," vol. 100, pp. 211-229, 2018. https://doi.org/10.1016/j.cor.2018.07.025.

[14] X. Liu, L. Wang, L. Kong, F. Li, and J. J. P. C. Li, "A Hybrid Genetic Algorithm for Minimizing Energy Consumption in Flow Shops Considering Ultra-low Idle State," vol. 80, pp. 192-196, 2019. https://doi.org/10.1016/j.procir.2018.12.013.

[15] T. Varadharajan and C. J. E. J. o. O. R. Rajendran, "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," vol. 167, pp. 772-795, 2005. https://doi.org/10.1016/j.ejor.2004.07.020.

[16] M. Bank, S. F. Ghomi, F. Jolai, and J. J. A. i. E. S. Behnamian, "Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration," vol. 47, pp. 1-6, 2012. https://doi.org/10.1016/j.advengsoft.2011.12.001.

[17] P. Jarosław, S. Czesław, and Ż. J. P. C. S. Dominik, "Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm," vol. 18, pp. 936-945, 2013. https://doi.org/10.1016/j.procs.2013.05.259.

[18] C.-J. Liao, C.-T. Tseng, P. J. C. Luarn, and O. Research, "A discrete version of particle swarm optimization for flowshop scheduling problems," vol. 34, pp. 3099-3111, 2007. https://doi.org/10.1016/j.cor.2005.11.017.

[19] S. Ponnambalam, N. Jawahar, and S. Chandrasekaran, "Discrete particle swarm optimization algorithm for flowshop scheduling," in Particle Swarm Optimization, ed: IntechOpen, 2009. https://www.intechopen.com/download/pdf/6275.

[20] F. P. Goksal, I. Karaoglan, F. J. C. Altiparmak, and I. Engineering, "A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery," vol. 65, pp. 39-53, 2013. https://doi.org/10.1016/j.cie.2012.01.005.

[21] X. Zheng, S. Zhou, and H. J. I. J. o. P. R. Chen, "Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes," vol. 57, pp. 3060-3079, 2019. https://doi.org/10.1080/00207543.2018.1529445.

[22] S. Sheikh, G. Komaki, V. J. C. Kayvanfar, and I. Engineering, "Multi objective two-stage assembly flow shop with release time," vol. 124, pp. 276-292, 2018. https://doi.org/10.1016/j.cie.2018.07.023.

[23] B. Jarraya and A. J. I. J. o. C. B. S. Bouri, "Metaheuristic optimization backgrounds: a literature review," vol. 3, 2012. https://ssrn.com/abstract=2114335.

[24] D. P. Ronconi and E. G. Birgin, "Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness," in Just-in-Time systems, ed: Springer, 2012, pp. 91-105. https://doi.org/10.1007/978-1-4614-1123-9_5.

[25] M. Clerc, "Discrete particle swarm optimization, illustrated by the traveling salesman problem," in New optimization techniques in engineering, ed: Springer, 2004, pp. 219-239. https://doi.org/10.1007/978-3-540-39930-8_8.

[26] B. Santosa and N. Siswanto, "Discrete particle swarm optimization to solve multi-objective limited-wait hybrid flow shop scheduling problem," in IOP Conference Series: Materials Science and Engineering, 2018, p. 012006. https://doi.org10.1088/1757-899x/337/1/012006.

[27] L. A. J. Zurich, "Operations Research in Production Planning, Scheduling and Inventory Control," Journal of the Operational Research Society, vol. 26, pp. 568-569, 1975. https://doi.org/10.1057/jors.1975.120.

[28] J. Kennedy and R. Eberhart, "Particle swarm optimization (PSO)," in Proc. IEEE International Conference on Neural Networks, Perth, Australia, 1995, pp. 1942-1948.

[29] Y. Shi and R. C. Eberhart, "Parameter selection in particle swarm optimization," in International conference on evolutionary programming, 1998, pp. 591-600. https://doi.org/10.1007/BFb0040810.

[30] R. Gangadharan and C. J. I. J. o. P. E. Rajendran, "Heuristic algorithms for scheduling in the no-wait flowshop," vol. 32, pp. 285-290, 1993. https://doi.org/10.1016/0925-5273(93)90042-J.




DOI: https://doi.org/10.22219/JTIUMM.Vol20.No2.105-116 | Abstract views : 276 | PDF views : 276 |

Copyright (c) 2019 Jurnal Teknik Industri

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.


 
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.