A General Variable Neighborhood Search Algorithm to Minimize Makespan of the Distributed Permutation Flowshop Scheduling Problem

Authors: G. M. Komaki, S. Mobin, E. Teymourian, S. Sheikh

Abstract:

This paper addresses minimizing the makespan of the distributed permutation flow shop scheduling problem. In this problem, there are several parallel identical factories or flowshops each with series of similar machines. Each job should be allocated to one of the factories and all of the operations of the jobs should be performed in the allocated factory. This problem has recently gained attention and due to NP-Hard nature of the problem, metaheuristic algorithms have been proposed to tackle it. Majority of the proposed algorithms require large computational time which is the main drawback. In this study, a general variable neighborhood search algorithm (GVNS) is proposed where several time-saving schemes have been incorporated into it. Also, the GVNS uses the sophisticated method to change the shaking procedure or perturbation depending on the progress of the incumbent solution to prevent stagnation of the search. The performance of the proposed algorithm is compared to the state-of-the-art algorithms based on standard benchmark instances.

Keywords: Distributed permutation flow shop, scheduling, makespan, general variable neighborhood search algorithm.

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

References:

[1] J. M. Framinan, J. N. Gupta, R. Leisten, “A review and classification of heuristics for permutation flow-shop scheduling with makespan objective,” J. Oper. Res. Soc., vol. 55, no. 12, pp. 1243-1255, July 2004.
[2] S. R. Hejazi, S. Saghafian, “Flowshop-scheduling problems with makespan criterion: a review,” Int. J. Prod. Res., vol. 43, no. 14, pp. 2895-2929, 2005.
[3] J. N. Gupta, E.F. Stafford, “Flowshop scheduling research after five decades,” Eur. J. Oper. Res., vol. 169, no. 3, pp. 699-711, March 2006.
[4] B. Naderi, R. Ruiz, “The distributed permutation flowshop scheduling problem,” Comput. Oper. Res., vol. 37, no. 4, pp. 754–768, April 2010.
[5] B. Naderi, R. Ruiz, “A scatter search algorithm for the distributed permutation flowshop scheduling problem,” Eur. J. Oper. Res., vol. 239, no. 2, pp. 323-334, December 2014.
[6] B. Ekşioğlu, S. D. Ekşioğlu, P. Jain, “A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods,” Comput. Ind. Eng., vol. 54, no. 1, pp. 1-11, February 2008.
[7] J. Grabowski, M. Wodecki, “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion,” Comput. Oper. Res., vol. 31, no. 11, pp. 1891-1909, September 2004.
[8] E. Nowicki, C. Smutnicki, “Some aspects of scatter search in the flowshop problem,” Eur. J. Oper. Res., vol. 169, no. 2, pp. 654-666, 2006
[9] M. Solimanpur, P. Vrat, R. Shankar, “A neuro-tabu search heuristic for the flow shop scheduling problem,” Comput. Oper. Res., vol. 31, no. 13,pp. 2151-2164, November 2004.
[10] V. Fernandez-Viagas, J. M. Framinan, “A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem,” Int. J. Prod. Res., vol. 53, no. 4, pp. 1111-1123, 2015.
[11] E. Nowicki, C. Smutnicki, “A fast tabu search algorithm for the permutation flow-shop problem,” Eur. J. Oper. Res., vol. 91, no. 1, pp. 160-175, September 1996.
[12] X. Dong, M. Nowak, P. Chen, Y. Lin, “Self-adaptive Perturbation and Multi-neighborhood Search for Iterated Local Search on the Permutation Flow Shop Problem,” Comput. Ind. Eng., vol. 87, pp. 176–185, September 2015.
[13] R. M’Hallah, “Minimizing total earliness and tardiness on a permutation flow shop using VNS and MIP,” Comput. Ind. Eng., vol. 75, pp. 142- 156, September 2014.
[14] R. M’Hallah, “An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop,” Int. J. Prod. Res., vol. 52, no. 13, pp. 3802-3819, 2014.
[15] J. Sánchez-Oro, J. J. Pantrigo, A. Duarte, “Combining intensification and diversification strategies in VNS. An application to the Vertex Separation problem,” Comput. Oper. Res., vol. 52, pp. 209-219, December 2014.
[16] N. Mladenovic, P. Hansen, Variable neighborhood search, Comput. Oper. Res., 24 (1997) 1097–1100.
[17] P. Hansen, N. Mladenović, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3,pp. 449-467,2001.
[18] P. Hansen, N. Mladenović, J.A.M. Pérez, “Variable neighbourhood search: methods and applications,” 4OR, vol. 6, no. 4, pp. 319-360, 2008.
[19] V. Fernandez-Viagas, J. M. Framinan, “A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem,” Int. J. Prod. Res., vol. 53, no. 4, pp. 1111-1123, 2015.
[20] X. Li, Q. Wang, C. Wu, “Heuristic for no-wait flow shops with makespan minimization,” Int. J. Prod. Res., vol. 46, no. 9, pp. 2519- 2530, 2008.
[21] R. Ruiz, T. Stützle, “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” Eur. J. Oper. Res., vol. 177, no. 3, pp. 2033-2049, March 2007.
[22] J. Gao, R. Chen, W. Deng, “An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem,” Int. J. Prod. Res., vol. 51, no. 3, pp. 641-651, 2013.
[23] S. W. Lin, K. C. Ying, C. Y. Huang, “Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm,” Int. J. Prod. Res., vol. 51, no. 16, pp. 5029-5038, 2013.
[24] S. Y. Wang, L. Wang, M. Liu, Y. Xu, “An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem,” Int. J. Prod. Econ., vol.145, no. 1, pp. 387-396, September 2013.
[25] Y. Xu, L. Wang, S. Wang, M. Liu, “An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem,” Eng. Optim., vol. 46, no. 9, pp. 1269-1283, 2014.
[26] E. Taillard, “Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem.” Eur. J. Oper. Res., vol. 47,no. 1, pp.65–74, 1990.