Minimizing Total Flow Time in a Flow Shop with Blocking Using a Hybrid Variable Neighborhood Search and Simulated Annealing Algorithm

Abstract:

In this paper, a hybrid methodology that incorporates a simulated annealing (SA) approach into the framework of variable neighborhood search (VNS) is proposed to solve the blocking flow shop scheduling problem with the total flow time minimization. The proposed hybrid algorithm adopts SA as the local search method in the third stage of VNS, and uses a perturbation mechanism consisting of three neighborhood operators in VNS to diversify the search. To enhance the intensification search, best-insert operator is adopted to generate the neighbors in SA. To evaluate the performance of the proposed hybrid algorithm, computational experiments and comparisons were conducted on the well-known Taillard’s benchmark problems. The computational results and comparisons validate the effectiveness of the proposed algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 631-632)
• Pages: 57-61
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.631-632.57
• Online since: September 2014
• Authors: Zhan Peng Xie, Chao Yong Zhang*, Xin Yu Shao, Yong Yin
• Keywords: Blocking Flow Shop, Simulated Annealing Algorithm, Total Flow Time, Variable Neighborhood Search

References

[1] R. Storn and K. Price: Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization Over Continuous Spaces. Journal of Global Optimization 11, 341–359 (1997).

[2] Allahverdi, C.T. Ng, T.C.E. Cheng , et al.: A Survey of Scheduling Problems with Setup Times or Costs. European Journal of Operational Research 187, 985–1032 (2008).

DOI: 10.1016/j.ejor.2006.06.060

[3] I.K. Abadi, N.G. Hall, C. Sriskandarajah: Minimizing cycle time in a blocking flowshop. Operations Research 48(1), 177-180 (2000).

DOI: 10.1287/opre.48.1.177.12451

[4] R. Leisten: Flowshop sequencing problems with limited buffer storage. The International Journal of Production Research 28(11), 2085-2100 (1990).

DOI: 10.1080/00207549008942855

[5] D.P. Ronconi, L.R. Henriques: Some heuristic algorithms for total tardiness minimization in a flowshop with blocking. Omega 37(2), 272-281 (2009).

DOI: 10.1016/j.omega.2007.01.003

[6] V. Caraffa, S. Ianes, T.P. Bagchi, C. Sriskandarajah: Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics 70(2), 101-115 (2001).

DOI: 10.1016/s0925-5273(99)00104-8

[7] J. Grabowski, J. Pempera: The permutation flow shop problem with blocking. A tabu search approach. Omega 35(3), 302-311 (2007).

DOI: 10.1016/j.omega.2005.07.004

[8] S.W. Lin, K.C. Ying: Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm. Omega 41(2), 383-389 (2013).

DOI: 10.1016/j.omega.2012.03.006

[9] L. Wang, Q.K. Pan, M.F. Tasgetiren: Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert Systems with Applications 37(12), 7929-7936 (2010).

DOI: 10.1016/j.eswa.2010.04.042

[10] Y.Y. Han, J.H. Duan, Y.J. Yang, M. Zhang, B. Yun. Minimizing the total flowtime flowshop with blocking using a discrete artificial bee colony. Advanced Intelligent Computing Theories and Applications With Aspects of Artificial Intelligence: Springer; (2012).

DOI: 10.1007/978-3-642-25944-9_12

[11] D.P. Ronconi,: A Note on Constructive Heuristics for the Flowshop Problem with Blocking. International Journal of Production Economics 87, 39–48 (2004).

DOI: 10.1016/s0925-5273(03)00065-3

[12] M. Nawaz, E.E.J. Enscore, I. Ham: A Heuristic Algorithm for The m-machine, n-job Flow Shop Sequencing Problem. International Journal of Management Science 11, 91–95 (1983).

DOI: 10.1016/0305-0483(83)90088-9