Hybrid Metaheuristics and Linear Programming for Finite Capacity MRP in Multi- Stage Flexible Flow Shop with Permutation and Non-permutation Scheduling Options
Article Sidebar
Published:
Aug 3, 2018
Keywords:
Finite capacity MRP Flexible flow shop Metaheuristic Linear programming Permutation scheduling Non-permutation scheduling
Main Article Content
Abstract
This paper presents a new algorithm for Finite Capacity MRP (FCMRP) in a multi-stage flexible flow shop. The proposed algorithm consists of four conventional metaheuristics namely, Genetic Algorithm (GA), Tabu Search (TS), Variable Neighborhood Search (VNS), and Simulated Annealing (SA) hybridized with Linear Programming (LP). The objective is to minimize the total cost, which is the sum of tardiness, earliness, and flow-time costs. There are two main steps of the proposed algorithm. Firstly, an efficient sequence of orders is generated by the proposed metaheuristics in a way that reduce the total cost. In this step, the required operations of the orders are scheduled based on two scheduling options called permutation and non-permutation. Secondly, the total cost is minimized by the LP model. The required parameters of the metaheuristics are tuned by using real data from automotive companies. The result shows that the proposed algorithm significantly outperforms the existing algorithm, and GA obtains the best total cost.
Article Details
How to Cite
Songserm, W., Wuttipornpun, T., & Jaturanonda, C. (2018). Hybrid Metaheuristics and Linear Programming for Finite Capacity MRP in Multi- Stage Flexible Flow Shop with Permutation and Non-permutation Scheduling Options. Applied Science and Engineering Progress, 11(3), 173–183. Retrieved from https://ph02.tci-thaijo.org/index.php/ijast/article/view/211333
Issue
Section
Research Articles
References
[1] P. B. Nagendra and S. K. Das, “Finite capacity scheduling method for MRP with lot size restrictions,” International Journal of Production Research, vol. 39, pp. 1603–1623, 2001.
[2] A. M. Örnek and O. Cengiz, “Capacitated lot sizing with alternative routings and overtime decisions,” International Journal of Production Research, vol. 44, no. 24, pp. 5363–5389, 2006.
[3] C. Öztürk and A. M. Örnek, “A MIP based heuristic for capacitated MRP systems,” Computers & Industrial Engineering, vol. 63, no. 4, pp. 926–942, 2012.
[4] N. A. Bakke and R. Hellberg, “The challenges of capacity planning,” International Journal of Production Economics, vol. 30–31, no. 1, pp. 243–264, 1993.
[5] S-H. Lee, S. Trimi, D. Choi, and J. S. Rha, “A comparative study of proprietary ERP and open source ERP modules on the value chain,” International Journal of Information and Decision Sciences, vol. 3, no. 1, pp. 26–38, 2011.
[6] T. Wuttipornpun and P. Yenradee, “Finite capacity material requirement planning system for assembly flow shop with alternative work centres,” International Journal of Industrial & Systems Engineering, vol. 18, no. 1, pp. 95–124, 2014.
[7] J. C. Chen, C-C. Wu, C-W. Chen, and K-H. Chen, “Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm,” Expert Systems with Applications, vol. 39, pp. 10016–10021, 2012.
[8] S. Wang and M. Liu, “A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem,” Computers & Operations Research, vol. 40, no. 4, pp. 1064–1075, 2013.
[9] H. F. Rahman, R. Sarker, and D. Essam, “A genetic algorithm for permutation flow shop scheduling under make to stock production system,” Computers & Industrial Engineering, vol. 90, no. 1, pp. 12–24, 2015.
[10] I-H. Kuo, S-J. Horng, T-W. Kao, T-L. Lin, C-L. Lee, T. Terano, and Y. Pan, “An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,” Expert Systems with Applications, vol. 36, pp. 7027–7032, 2009.
[11] D. Tang, M. Dai, M. A. Salido, and A. Giret, “Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization,” Computers in Industry, vol. 81, pp. 82–95, 2016.
[12] M. Eddaly, B. Jarboui, and P. Siarry, “Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem,” Journal of Computational Design and Engineering, vol. 3, no. 4, pp. 295–311, 2016.
[13] B. Yagmahan and M. M. Yenisey, “A multiobjective ant colony system algorithm for flow shop scheduling problem,” Expert Systems with Applications, vol. 37, pp. 1361–1368, 2010.
[14] F. Ahmadizar, “A new ant colony algorithm for makespan minimization in permutation flow shops,” Computers & Industrial Engineering, vol. 63, no. 2, pp. 355–361, 2012.
[15] Z. Zhang and Z. Jing, “An improved ant colony optimization algorithm for permutation flow shop scheduling to minimize makespan,” in Proceedings 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, 2012, pp. 605–609.
[16] M. K. Marichelvam, T. Prabaharan, and X. S. Yang, “Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan,” Applied Soft Computing, vol. 19, pp. 93–101, 2014.
[17] P. Dasgupta and S. Das, “A discrete inter-species cuckoo search for flowshop scheduling problems,” Computers & Operations Research, vol. 60, pp. 111–120, 2015.
[18] G. M. Komaki, E. Teymourian, V. Kayvanfar, and Z. Booyavi, “Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem,” Computers & Industrial Engineering, vol. 105, pp. 158–173, 2017.
[19] J. Grabowski and J. Pempera, “The permutation flow shop problem with blocking: A tabu search approach,” International Journal of Management Science, vol. 35, no. 3, pp. 302–311, 2007.
[20] J-S. Chen, J. C-H. Pan, and C-K. Wu, “Hybrid tabu search for re-entrant permutation flowshop scheduling problem,” Expert Systems with Applications, vol. 34, no. 3, pp. 1924–1930, 2008.
[21] L-M. Liao and C-J. Huang, “Tabu search heuristic for two-machine flowshop with batch processing machines,” Computers & Industrial Engineering, vol. 60, no. 3, pp. 426–432, 2011.
[22] W. Bozejko, J. Pempera, and C. Smutnicki, “Parallel tabu search algorithm for the hybrid flow shop problem,” Computers & Industrial Engineering, vol. 65, no. 3, pp. 466–474, 2013.
[23] Q-K. Pan and R. Ruiz, “Local search methods for the flowshop scheduling problem with flowtime minimization,” European Journal of Operational Research, vol. 222, no. 1 pp. 31–43, 2012.
[24] X. Dong, P. Chen, H. Huang, and M. Nowak, “A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time,” Computers & Operations Research, vol. 40, no. 2, pp. 627-632, 2013.
[25] Y. Wang, X. Dong, P. Chen, and Y. Lin, “Iterated local search algorithms for the sequence-dependent setup times flow shop scheduling problem minimizing makespan,” Foundation of Intelligent Systems, vol. 277, pp. 329–338, 2014.
[26] J. Xua, C-C. Wub, Y. Yinc, and W-C. Lin, “An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times,” Applied Soft Computing, vol. 52, pp. 39–47, 2017.
[27] W. E. Costa, M. C. Goldbarg, and E. G. Goldbarg, “Expert systems with applications,” Applied Soft Computing, vol. 39, no. 9, pp. 8149–8161, 2012.
[28] R. M. Hallah, “Minimizing total earliness and tardiness on a permutation flow shop using VNS and MIP,” Computers & Industrial Engineering, vol. 75, pp. 142–156, 2014.
[29] D. Lei, “Variable neighborhood search for twoagent flow shop scheduling problem,” Computers & Industrial Engineering, vol. 80, pp. 125–131, 2015.
[30] A. P. Rifai, H-T. Nguyen, and S. Z. M. Dawal, “Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling” Applied Soft Computing, vol. 40, pp. 42–57, 2016.
[31] C. Low, “Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines,” Computers & Operations Research, vol. 32, no. 8, pp. 2013–2025, 2005.
[32] B. Naderi, R. T. Moghaddam, and M. Khalili, “Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan,” Knowledge-Based Systems, vol. 23, no. 2, pp. 77–85, 2010.
[33] P. Jarosław, S. Czeslaw, and Z. Domonik, “Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm,” Procedia Computer Science, vol. 18, pp. 936–945, 2013.
[34] F. Nikzad, J. Rezaeian, I. Mahdavi, and I. Rastgar, “Scheduling of multi-component products in a two-stage flexible flow shop,” Applied Soft Computing, vol. 32, pp. 132–143, 2015.
[35] F. W. Glover and G. A. Kochenberger, Handbook of Metaheuristics. New York: Springer, 2003.
[36] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics. 2nd ed., New York: Springer, 2010.
[2] A. M. Örnek and O. Cengiz, “Capacitated lot sizing with alternative routings and overtime decisions,” International Journal of Production Research, vol. 44, no. 24, pp. 5363–5389, 2006.
[3] C. Öztürk and A. M. Örnek, “A MIP based heuristic for capacitated MRP systems,” Computers & Industrial Engineering, vol. 63, no. 4, pp. 926–942, 2012.
[4] N. A. Bakke and R. Hellberg, “The challenges of capacity planning,” International Journal of Production Economics, vol. 30–31, no. 1, pp. 243–264, 1993.
[5] S-H. Lee, S. Trimi, D. Choi, and J. S. Rha, “A comparative study of proprietary ERP and open source ERP modules on the value chain,” International Journal of Information and Decision Sciences, vol. 3, no. 1, pp. 26–38, 2011.
[6] T. Wuttipornpun and P. Yenradee, “Finite capacity material requirement planning system for assembly flow shop with alternative work centres,” International Journal of Industrial & Systems Engineering, vol. 18, no. 1, pp. 95–124, 2014.
[7] J. C. Chen, C-C. Wu, C-W. Chen, and K-H. Chen, “Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm,” Expert Systems with Applications, vol. 39, pp. 10016–10021, 2012.
[8] S. Wang and M. Liu, “A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem,” Computers & Operations Research, vol. 40, no. 4, pp. 1064–1075, 2013.
[9] H. F. Rahman, R. Sarker, and D. Essam, “A genetic algorithm for permutation flow shop scheduling under make to stock production system,” Computers & Industrial Engineering, vol. 90, no. 1, pp. 12–24, 2015.
[10] I-H. Kuo, S-J. Horng, T-W. Kao, T-L. Lin, C-L. Lee, T. Terano, and Y. Pan, “An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,” Expert Systems with Applications, vol. 36, pp. 7027–7032, 2009.
[11] D. Tang, M. Dai, M. A. Salido, and A. Giret, “Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization,” Computers in Industry, vol. 81, pp. 82–95, 2016.
[12] M. Eddaly, B. Jarboui, and P. Siarry, “Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem,” Journal of Computational Design and Engineering, vol. 3, no. 4, pp. 295–311, 2016.
[13] B. Yagmahan and M. M. Yenisey, “A multiobjective ant colony system algorithm for flow shop scheduling problem,” Expert Systems with Applications, vol. 37, pp. 1361–1368, 2010.
[14] F. Ahmadizar, “A new ant colony algorithm for makespan minimization in permutation flow shops,” Computers & Industrial Engineering, vol. 63, no. 2, pp. 355–361, 2012.
[15] Z. Zhang and Z. Jing, “An improved ant colony optimization algorithm for permutation flow shop scheduling to minimize makespan,” in Proceedings 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, 2012, pp. 605–609.
[16] M. K. Marichelvam, T. Prabaharan, and X. S. Yang, “Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan,” Applied Soft Computing, vol. 19, pp. 93–101, 2014.
[17] P. Dasgupta and S. Das, “A discrete inter-species cuckoo search for flowshop scheduling problems,” Computers & Operations Research, vol. 60, pp. 111–120, 2015.
[18] G. M. Komaki, E. Teymourian, V. Kayvanfar, and Z. Booyavi, “Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem,” Computers & Industrial Engineering, vol. 105, pp. 158–173, 2017.
[19] J. Grabowski and J. Pempera, “The permutation flow shop problem with blocking: A tabu search approach,” International Journal of Management Science, vol. 35, no. 3, pp. 302–311, 2007.
[20] J-S. Chen, J. C-H. Pan, and C-K. Wu, “Hybrid tabu search for re-entrant permutation flowshop scheduling problem,” Expert Systems with Applications, vol. 34, no. 3, pp. 1924–1930, 2008.
[21] L-M. Liao and C-J. Huang, “Tabu search heuristic for two-machine flowshop with batch processing machines,” Computers & Industrial Engineering, vol. 60, no. 3, pp. 426–432, 2011.
[22] W. Bozejko, J. Pempera, and C. Smutnicki, “Parallel tabu search algorithm for the hybrid flow shop problem,” Computers & Industrial Engineering, vol. 65, no. 3, pp. 466–474, 2013.
[23] Q-K. Pan and R. Ruiz, “Local search methods for the flowshop scheduling problem with flowtime minimization,” European Journal of Operational Research, vol. 222, no. 1 pp. 31–43, 2012.
[24] X. Dong, P. Chen, H. Huang, and M. Nowak, “A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time,” Computers & Operations Research, vol. 40, no. 2, pp. 627-632, 2013.
[25] Y. Wang, X. Dong, P. Chen, and Y. Lin, “Iterated local search algorithms for the sequence-dependent setup times flow shop scheduling problem minimizing makespan,” Foundation of Intelligent Systems, vol. 277, pp. 329–338, 2014.
[26] J. Xua, C-C. Wub, Y. Yinc, and W-C. Lin, “An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times,” Applied Soft Computing, vol. 52, pp. 39–47, 2017.
[27] W. E. Costa, M. C. Goldbarg, and E. G. Goldbarg, “Expert systems with applications,” Applied Soft Computing, vol. 39, no. 9, pp. 8149–8161, 2012.
[28] R. M. Hallah, “Minimizing total earliness and tardiness on a permutation flow shop using VNS and MIP,” Computers & Industrial Engineering, vol. 75, pp. 142–156, 2014.
[29] D. Lei, “Variable neighborhood search for twoagent flow shop scheduling problem,” Computers & Industrial Engineering, vol. 80, pp. 125–131, 2015.
[30] A. P. Rifai, H-T. Nguyen, and S. Z. M. Dawal, “Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling” Applied Soft Computing, vol. 40, pp. 42–57, 2016.
[31] C. Low, “Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines,” Computers & Operations Research, vol. 32, no. 8, pp. 2013–2025, 2005.
[32] B. Naderi, R. T. Moghaddam, and M. Khalili, “Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan,” Knowledge-Based Systems, vol. 23, no. 2, pp. 77–85, 2010.
[33] P. Jarosław, S. Czeslaw, and Z. Domonik, “Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm,” Procedia Computer Science, vol. 18, pp. 936–945, 2013.
[34] F. Nikzad, J. Rezaeian, I. Mahdavi, and I. Rastgar, “Scheduling of multi-component products in a two-stage flexible flow shop,” Applied Soft Computing, vol. 32, pp. 132–143, 2015.
[35] F. W. Glover and G. A. Kochenberger, Handbook of Metaheuristics. New York: Springer, 2003.
[36] M. Gendreau and J.-Y. Potvin, Handbook of Metaheuristics. 2nd ed., New York: Springer, 2010.