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

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.

Authors:

• G. M. Komaki
• S. Mobin
• E. Teymourian
• S. Sheikh

Keywords:

• Distributed permutation flow shop
• scheduling
• makespan
• general variable neighborhood search algorithm.

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.