Non-Population Search Algorithms for Capacitated Material Requirement Planning in Multi-Stage Assembly Flow Shop with Alternative Machines

Authors: Watcharapan Sukkerd, Teeradej Wuttipornpun

Abstract:

This paper aims to present non-population search algorithms called tabu search (TS), simulated annealing (SA) and variable neighborhood search (VNS) to minimize the total cost of capacitated MRP problem in multi-stage assembly flow shop with two alternative machines. There are three main steps for the algorithm. Firstly, an initial sequence of orders is constructed by a simple due date-based dispatching rule. Secondly, the sequence of orders is repeatedly improved to reduce the total cost by applying TS, SA and VNS separately. Finally, the total cost is further reduced by optimizing the start time of each operation using the linear programming (LP) model. Parameters of the algorithm are tuned by using real data from automotive companies. The result shows that VNS significantly outperforms TS, SA and the existing algorithm.

Keywords: Capacitated MRP, non-population search algorithms, linear programming, assembly flow shop.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129714

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] M. Zandieh, and N. Karimi, “An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times,” Journal of Intelligent Manufacturing, vol. 22 no. 6, pp. 979-989, 2011.
[8] P-C. Chang, W-H. Huang, J-L. Wu, and T. C. E. Cheng, “A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem,” International Journal of Production Economics, vol. 141 no. 1, pp. 45-55, 2013.
[9] K-W. Pang, “A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness,” International Journal of Production Economics, vol. 141 no. 1, pp. 127-136, 2013.
[10] C. Zhang, J. Sun, X. Zhu, and Q. Yang, “An improved particle swarm optimization algorithm for flowshop scheduling problem,” Information Processing Letters, vol. 108 no. 4, pp. 204-209, 2008.
[11] L. Tang, and X. Wang, “An Improved Particle Swarm Optimization Algorithm for the Hybrid Flowshop Scheduling to Minimize Total Weighted Completion Time in Process Industry,” Transactions on Control Systems Technology, vol. 18 no. 6, pp. 1303-1313, 2010.
[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] Y. Gajpal, and C. Rajendran, “An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshop,” International Journal of Production Economics, vol. 101 no. 2, pp. 259-272, 2006.
[14] B. Yagmahan, and M. M. Yenisey, “A multi-objective ant colony system algorithm for flow shop scheduling problem,” Expert Systems with Applications, vol. 37 no. 2, pp. 1361-1368, 2010.
[15] Z. Zhang, and Z. Jing, “An improved ant colony optimization algorithm for permutation flow shop scheduling to minimize makespan,” 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 605-609, 2012.
[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] H. Wang, W. Wang, H. Sun, Z. Cui, S. Rahnamayan, and S. Zeng, “A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems,” Soft Computing, Springer-Verlag Berlin Heidelberg, pp. 1-11, 2016.
[19] B. Ekşioğlu, S. D. Ekşioğlu, and P. Jain, “A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods,” Computers & Industrial Engineering, vol. 54, no. 1, pp. 1-11, 2008.
[20] X. Wang, and L. Tang, “A tabu search heuristic for the hybrid flow shop scheduling with finite intermediat buffers,” Computers & Operations Research, vol. 36, no. 3, pp. 907-918, 2009.
[21] 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, no. 3, pp. 1924-1930, 2008.
[22] 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.
[23] X. Dong, P. Chen, and H. Huang, “An Improved Iterated Local Search Algorithm for the Permutation Flowshop Problem with Total Flowtime,” Advance in Automation and Robotics, Springer Berlin Heidelberg, vol. 1, pp. 41-48, 2011.
[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] I. Ribas, R. Companys, and X. Tort-Martorell, “An efficient iterated local search algorithm for the total tardiness blocking flow shop problem,” International Journal of Production Research, vol.51, no. 17, pp. 5238-5252, 2013.
[27] J-Q. Li, Q-K. Pan, and F-T. Wang, “A hybrid variable neighborhood search for solving the hybrid flowshop scheduling problem,” Applied Soft Computing, vol. 24, pp. 63-77, 2014.
[28] G. Moslehi, and D. Khorasanian, “A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion,” Computers & Operations Research, vol. 52, pp. 260-268, 2014.
[29] 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.
[30] D. Lei, “Variable neighborhood search for two-agent flow shop scheduling problem,” Computers & Industrial Engineering, vol. 80, pp. 125-131, 2015.
[31] J. Jungwattanakit, M. Reodecha, P. Chaovalitwongse, and F. Werner, “A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria,” Computers & Operations Research, vol. 36, pp. 358-378, 2009.
[32] R. Zhang, and C. Wu, “A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective,” Computers & Operations Research, vol. 38, pp. 854-867, 2011.
[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.