The Discrete Particle Swarm Optimization Algorithms for Permutation Flowshop Scheduling Problem
DOI:
https://doi.org/10.22219/JTIUMM.Vol20.No2.105-116Keywords:
Flow shop, Earliness, Tardiness, Metaheuristic, Particle swarm optimizationAbstract
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 was that 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 the proposed algorithm can solve the problem well in a short computational time. 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 impact the quality of solutions produced by HDPSO and MPSO algorithms.
Downloads
References
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.
M. Avriel, M. Penn, and N. J. D. A. M. Shpirer, "Container ship stowage problem: complexity and connection to the coloring of circle graphs," Discrete Applied Mathematics, vol. 103, pp. 271-279, 2000. https://doi.org/10.1016/S0166-218X(99)00245-0.
V. A. Armentano and J. E. Claudio, "An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem," Journal of Heuristics, vol. 10, pp. 463-481, 2004. https://doi.org/10.1023/B:HEUR.0000045320.79875.e3.
J.-S. Chen, J. C.-H. Pan, and C.-K. Wu, "Hybrid tabu search for re-entrant permutation flow-shop scheduling problem," Expert Systems with Applications, vol. 34, pp. 1924-1930, 2008. https://doi.org/10.1016/j.eswa.2007.02.027.
B. Ekşioğlu, S. D. Ekşioğlu, and P. C. Jain, "A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods," Computers & Industrial Engineering, vol. 54, pp. 1-11, 2008. https://doi.org/10.1016/j.cie.2007.04.004.
F. S. Erenay, I. Sabuncuoglu, A. Toptal, and M. K. Tiwari, "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," European Journal of Operational Research, vol. 201, pp. 89-98, 2010. https://doi.org/10.1016/j.ejor.2009.02.014.
Y. Marinakis, and M. J. C. Marinaki, "A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem," Computers & Operations Research, vol. 37, pp. 432-442, 2010. https://doi.org/10.1016/j.cor.2009.03.004.
C.-W. Chiou, W.-M. Chen, C.-M. Liu, and M.-C. Wu, "A genetic algorithm for scheduling dual flow shops," Expert Systems with Applications, vol. 39, pp. 1306-1314, 2012. https://doi.org/10.1016/j.eswa.2011.08.008.
W.-H. Wu, W.-H. Wu, J.-C. Chen, W.-C. Lin, J. Wu, and C.-C. Wu, "A heuristic-based genetic algorithm for the two-machine flowshop scheduling with learning consideration," Journal of Manufacturing Systems, vol. 35, pp. 223-233, 2015. https://doi.org/10.1016/j.jmsy.2015.02.002.
N. Karimi, and H. J. C. Davoudpour, "A high performing metaheuristic for multi-objective flowshop scheduling problem," Computers & operations research, vol. 52, pp. 149-156, 2014. https://doi.org/10.1016/j.cor.2014.01.006.
H. F. Rahman, R. Sarker, and D. Essam, "A genetic algorithm for permutation flowshop scheduling under practical make-to-order production system," Computers & Industrial Engineering, vol. 31, pp. 87-103, 2017. https://doi.org/10.1017/S0890060416000196.
S. A. Basir, M. M. Mazdeh, and M. J. C. Namakshenas, "Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system," Computers & Industrial Engineering, vol. 126, pp. 217-231, 2018. https://doi.org/10.1016/j.cie.2018.09.035.
C. Yu, Q. Semeraro, and A. J. C. Matta, "A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility," Computers & Operations Research, vol. 100, pp. 211-229, 2018. https://doi.org/10.1016/j.cor.2018.07.025.
X. Liu, L. Wang, L. Kong, F. Li, and J. J. Li, "A Hybrid Genetic Algorithm for Minimizing Energy Consumption in Flow Shops Considering Ultra-low Idle State," Procedia CIRP, vol. 80, pp. 192-196, 2019. https://doi.org/10.1016/j.procir.2018.12.013.
T. Varadharajan and C. J. Rajendran, "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," European Journal of Operational Research, vol. 167, pp. 772-795, 2005. https://doi.org/10.1016/j.ejor.2004.07.020.
M. Bank, S. F. Ghomi, F. Jolai, and J. Behnamian, "Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration," Advances in Engineering Software, vol. 47, pp. 1-6, 2012. https://doi.org/10.1016/j.advengsoft.2011.12.001.
P. Jarosław, S. Czesław, and Ż. Dominik, "Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm," Procedia Computer Science, vol. 18, pp. 936-945, 2013. https://doi.org/10.1016/j.procs.2013.05.259.
C.-J. Liao, C.-T. Tseng, and P. Luarn, "A discrete version of particle swarm optimization for flowshop scheduling problems," Computers & Operations Research, vol. 34, pp. 3099-3111, 2007. https://doi.org/10.1016/j.cor.2005.11.017.
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.
F. P. Goksal, I. Karaoglan, and F. Altiparmak, "A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery," Computers & Industrial Engineering, vol. 65, pp. 39-53, 2013. https://doi.org/10.1016/j.cie.2012.01.005.
X. Zheng, S. Zhou, and H. Chen, "Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes," International Journal of Production Research, vol. 57, pp. 3060-3079, 2019. https://doi.org/10.1080/00207543.2018.1529445.
S. Sheikh, G. Komaki, and V. Kayvanfar, "Multi objective two-stage assembly flow shop with release time," Computers & Industrial Engineering, vol. 124, pp. 276-292, 2018. https://doi.org/10.1016/j.cie.2018.07.023.
B. Jarraya and A. Bouri, "Metaheuristic optimization backgrounds: a literature review," International Journal of Contemporary Business Studies, vol. 3, pp. 31-44, 2012. https://ssrn.com/abstract=2114335.
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.
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.
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.
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.
J. Kennedy and R. Eberhart, "Particle swarm optimization (PSO)," in Proc. IEEE International Conference on Neural Networks, Perth, Australia, 1995, pp. 1942-1948.
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.
R. Gangadharan and C. Rajendran, "Heuristic algorithms for scheduling in the no-wait flowshop," International Journal of Production Economics, vol. 32, pp. 285-290, 1993. https://doi.org/10.1016/0925-5273(93)90042-J.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Ikhlasul Amallynda
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
