Bi-objective Hybrid Flow Shop Scheduling with Family Setup Times Using Hybrid Genetic and Migrating Birds Optimization Algorithms
Article Sidebar
Published:
Jan 4, 2021
Keywords:
Hybrid flow shop scheduling Family setup times NSGA-II Migrating birds optimization Hybrid algorithm
Main Article Content
Abstract
This paper presents a hybrid metaheuristic algorithm to solve the hybrid flow shop scheduling problem (HFSP) with family setup times. Many conditions of HFSP have been extensively studied in recently years and metaheuristics and local search algorithms have also been developed to yield better solutions for multi-objective HFSP. HFSP in this work is based on a harddisk drive manufacturer. An effective NSGA-II integrated with migrating birds optimization (MBO) called MBNSGA-II is proposed to improve the quality of solutions for bi-objective HFSP. Makespan and total tardiness time are the objectives of this HFSP. MBO is added to mutation operation of genetic algorithm to improve the Pareto front. Next, various sizes of benchmark problem are utilized to evaluate the performance of NSGA-II and MBNSGA-II. The comparisons of two algorithms consisting of NSGA-II and MBNSGA-II are provided by using the numerical examples. It is obvious the Pareto fronts obtained from MBNSGA-II are adjacent to the approximated true Pareto front. In terms of inverted generational distance (IGD) which is the index of convergence and diversity of the solution set, the performance of proposed MBNSGA-II outperforms NSGA-II.
Article Details
How to Cite
Laoraksakiat, W., & Asawarungsaengkul, K. (2021). Bi-objective Hybrid Flow Shop Scheduling with Family Setup Times Using Hybrid Genetic and Migrating Birds Optimization Algorithms. Applied Science and Engineering Progress, 14(1), 19–30. https://doi.org/10.14416/j.asep.2019.10.001
Issue
Section
Research Articles
References
[1] J. E. Schaller, “Minimizing total tardiness for scheduling identical parallel machines with family setups,” Computers & Industrial Engineering, vol. 72, pp. 274–281, 2014.
[2] M. A. Bozorgirad and R. Logendran, “Bicriteria group scheduling in hybrid flowshops,” International Journal of Production Economics, vol. 145, pp. 599–612, 2013.
[3] J. Behnamian and S. M. T. F. Ghomi, “Hybrid flowshop scheduling with machine and resourcedependent processing times,” Applied Mathematical Modelling, vol. 35, pp. 1107–1123, 2011.
[4] H.-M. Cho, S. J. Bae, J. Kim, and I.-J. Jeong, “Biobjective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm,” Computers & Industrial Engineering, vol. 61, pp. 529–541, 2011.
[5] F. Dugardin, L. Amodeo, and F. Yalaoui, “Multiobjective scheduling of a reentrant hybrid flowshop,” in Proceeding 2009 International Conference on Computers & Industrial Engineering, 2009, pp.193–198.
[6] K.-C. Ying, S.-W. Lin, and S.-Y. Wan, “Bi-objective reentrant hybrid flowshop scheduling: An iterated Pareto greedy algorithm,” International Journal of Production Research, vol. 52, no. 19, pp. 5735–5747, 2014.
[7] S. H. Abyaneh and M. Zandieh, “Bi-objective hybrid flow shop scheduling with sequence dependent setup times and limited buffers,” The International Journal of Advanced Manufacturing Technology, vol. 58, pp. 309–325, 2012.
[8] S. M. Mousavi, M. Zandieh, and M. Amiri, “Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequencedependent setup times,” International Journal of Production Research, vol. 50, no. 10, pp. 2570–2591, 2012.
[9] H. Wang, Y. Fu, M. Huang, G. Q. Quang, and J. Wang, “NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem,” Computers & Industrial Engineering, vol. 113, pp. 185–194, 2017.
[10] X. Li, H. Checade, F. Yalaoui, and L. Amodeo, “Lorenz dominance based metaheuristic to solve a hybrid flowshop scheduling problem with sequence dependent setup times,” in Proceeding of 2011 International Conference on Communications, Computing and Control Applications, 2011, pp. 1–6.
[11] D. Lei and Y. Zheng, “Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search,” Applied Soft Computing, vol. 61, pp. 122–128, 2017.
[12] Q.-K. Pan, L. Wang, J.-Q. Li, and J.-H. Duan, “A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization,” Omega, vol. 45 pp. 42–56, 2014.
[13] X. Wang and L. Tang, “A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers,” Computers & Operations Research, vol. 36, pp. 907–918, 2009.
[14] S. Su, H. Yu, Z. Wu, and W. Tian, “A distributed coevolutionary algorithm for multiobjective hybrid flowshop scheduling problems,” The International Journal of Advanced Manufacturing Technology, vol. 70, pp. 477–494, 2014.
[15] E. L. Solano-Charris, J. R. Montoya-Torres, and C. D. Paternina-Arboleda, “Ant colony optimization algorithm for a Bi-criteria 2-stage hybrid flowshop scheduling problem,” Journal of Intelligent Manufacturing, vol 22, pp. 815–822, 2011.
[16] J.-Q. Li and Q.-K. Pan, “Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm,” Information Sciences, vol. 316, pp. 487–502, 2015.
[17] E. Duman, M. Uysal, and A. F. Alkaya, “Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem,” Information Sciences, vol. 217, pp. 65–77, 2012.
[18] Q.-K. Pan and Y. Dong, “An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimization,” Information Sciences, vol. 277, pp. 643–655, Sep. 2014.
[19] B. Zhang,Q.-K. Pan, L. Gao, X.-L. Zhang, H.-Y. Sang, and J.-Q. Li, “An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming,” Applied Soft Computing, vol. 52, pp. 14–27, 2017.
[20] T. Meng, Q.-K. Pan, J.-Q. Li, and H.-Y. Sang, “An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem,” Swarm and Evolutionary Computation, vol. 38, pp. 64–78, 2018.
[21] A. Sioud and C. Gagné, “Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times,” European Journal of Operational Research, vol. 264, pp. 66–73, 2018.
[22] L. Gao and Q.-K. Pan, “A shuffled multi-swarm micro-migrating birds optimizer for a multiresource- constrained flexible job shop scheduling problem,” Information Sciences, vol. 372, pp. 655–676, 2016.
[23] B. Zhang, Q.-K. Pan, L. Gao, X.-L. Zhang, and K.-K. Peng, “A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem,” Soft Computing, pp. 1–29, 2018.
[24] T. Sawik, Scheduling in Supply Chains Using Mixed Integer Programming. New Jersey: John Wiley and Sons, 2011.
[25] K. Deb, A. Pratap, S. Agarwal, and T. A. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
[26] M. Gholami, M. Zandieh, and A. Alem-Tabriz, “Scheduling hybrid flow shop with sequencedependent setup times and machines with random breakdowns,” The International Journal of Advanced Manufacturing Technology, vol. 42, pp. 189–201, 2009.
[27] N. Karimi and H. Davoupour, “Multi-objective colonial competitive algorithm for hybrid flowshop problem,” Applied Soft Computing, vol. 49, pp. 725–733, 2016.
[28] C. A. C. Coello and N. C. Cort´es, “Solving multiobjective optimization problems using an artificial immune system,” Genetic Programming and Evolvable Machines, vol. 6, no. 2, pp. 163–190, 2005.
[29] J. R. Schott, “Fault tolerant design using single and multicriteria genetic algorithm optimization,” M.S. thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, MA, USA, 1995.
[2] M. A. Bozorgirad and R. Logendran, “Bicriteria group scheduling in hybrid flowshops,” International Journal of Production Economics, vol. 145, pp. 599–612, 2013.
[3] J. Behnamian and S. M. T. F. Ghomi, “Hybrid flowshop scheduling with machine and resourcedependent processing times,” Applied Mathematical Modelling, vol. 35, pp. 1107–1123, 2011.
[4] H.-M. Cho, S. J. Bae, J. Kim, and I.-J. Jeong, “Biobjective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm,” Computers & Industrial Engineering, vol. 61, pp. 529–541, 2011.
[5] F. Dugardin, L. Amodeo, and F. Yalaoui, “Multiobjective scheduling of a reentrant hybrid flowshop,” in Proceeding 2009 International Conference on Computers & Industrial Engineering, 2009, pp.193–198.
[6] K.-C. Ying, S.-W. Lin, and S.-Y. Wan, “Bi-objective reentrant hybrid flowshop scheduling: An iterated Pareto greedy algorithm,” International Journal of Production Research, vol. 52, no. 19, pp. 5735–5747, 2014.
[7] S. H. Abyaneh and M. Zandieh, “Bi-objective hybrid flow shop scheduling with sequence dependent setup times and limited buffers,” The International Journal of Advanced Manufacturing Technology, vol. 58, pp. 309–325, 2012.
[8] S. M. Mousavi, M. Zandieh, and M. Amiri, “Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequencedependent setup times,” International Journal of Production Research, vol. 50, no. 10, pp. 2570–2591, 2012.
[9] H. Wang, Y. Fu, M. Huang, G. Q. Quang, and J. Wang, “NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem,” Computers & Industrial Engineering, vol. 113, pp. 185–194, 2017.
[10] X. Li, H. Checade, F. Yalaoui, and L. Amodeo, “Lorenz dominance based metaheuristic to solve a hybrid flowshop scheduling problem with sequence dependent setup times,” in Proceeding of 2011 International Conference on Communications, Computing and Control Applications, 2011, pp. 1–6.
[11] D. Lei and Y. Zheng, “Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search,” Applied Soft Computing, vol. 61, pp. 122–128, 2017.
[12] Q.-K. Pan, L. Wang, J.-Q. Li, and J.-H. Duan, “A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization,” Omega, vol. 45 pp. 42–56, 2014.
[13] X. Wang and L. Tang, “A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers,” Computers & Operations Research, vol. 36, pp. 907–918, 2009.
[14] S. Su, H. Yu, Z. Wu, and W. Tian, “A distributed coevolutionary algorithm for multiobjective hybrid flowshop scheduling problems,” The International Journal of Advanced Manufacturing Technology, vol. 70, pp. 477–494, 2014.
[15] E. L. Solano-Charris, J. R. Montoya-Torres, and C. D. Paternina-Arboleda, “Ant colony optimization algorithm for a Bi-criteria 2-stage hybrid flowshop scheduling problem,” Journal of Intelligent Manufacturing, vol 22, pp. 815–822, 2011.
[16] J.-Q. Li and Q.-K. Pan, “Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm,” Information Sciences, vol. 316, pp. 487–502, 2015.
[17] E. Duman, M. Uysal, and A. F. Alkaya, “Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem,” Information Sciences, vol. 217, pp. 65–77, 2012.
[18] Q.-K. Pan and Y. Dong, “An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimization,” Information Sciences, vol. 277, pp. 643–655, Sep. 2014.
[19] B. Zhang,Q.-K. Pan, L. Gao, X.-L. Zhang, H.-Y. Sang, and J.-Q. Li, “An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming,” Applied Soft Computing, vol. 52, pp. 14–27, 2017.
[20] T. Meng, Q.-K. Pan, J.-Q. Li, and H.-Y. Sang, “An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem,” Swarm and Evolutionary Computation, vol. 38, pp. 64–78, 2018.
[21] A. Sioud and C. Gagné, “Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times,” European Journal of Operational Research, vol. 264, pp. 66–73, 2018.
[22] L. Gao and Q.-K. Pan, “A shuffled multi-swarm micro-migrating birds optimizer for a multiresource- constrained flexible job shop scheduling problem,” Information Sciences, vol. 372, pp. 655–676, 2016.
[23] B. Zhang, Q.-K. Pan, L. Gao, X.-L. Zhang, and K.-K. Peng, “A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem,” Soft Computing, pp. 1–29, 2018.
[24] T. Sawik, Scheduling in Supply Chains Using Mixed Integer Programming. New Jersey: John Wiley and Sons, 2011.
[25] K. Deb, A. Pratap, S. Agarwal, and T. A. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
[26] M. Gholami, M. Zandieh, and A. Alem-Tabriz, “Scheduling hybrid flow shop with sequencedependent setup times and machines with random breakdowns,” The International Journal of Advanced Manufacturing Technology, vol. 42, pp. 189–201, 2009.
[27] N. Karimi and H. Davoupour, “Multi-objective colonial competitive algorithm for hybrid flowshop problem,” Applied Soft Computing, vol. 49, pp. 725–733, 2016.
[28] C. A. C. Coello and N. C. Cort´es, “Solving multiobjective optimization problems using an artificial immune system,” Genetic Programming and Evolvable Machines, vol. 6, no. 2, pp. 163–190, 2005.
[29] J. R. Schott, “Fault tolerant design using single and multicriteria genetic algorithm optimization,” M.S. thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, MA, USA, 1995.