An Iterated Greedy Algorithm for Solving the Blocking Flow Shop Scheduling Problem with Total Flow Time Criteria 
International Journal of Industrial Engineering & Production Research
December 2012, Volume 23, Number 4
pp. 301-308
ISSN: 2008-4889
http://IJIEPR.iust.ac.ir/
An Iterated Greedy Algorithm for Solving the Blocking Flow Shop Scheduling Problem with Total Flow Time Criteria
D. Khorasanian & G. Moslehi*
Danial Khorasanian is an M.S. Student of Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran Ghasem Moslehi is a Professor of Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran
KEYWORDS
Constructive heuristic, Iterated greedy algorithm, Blocking flow shop, Total flow time
ABSTRACT
In this paper, we propose an iterated greedy algorithm for solving the blocking flow shop scheduling problem with total flow time minimization objective. The steps of this algorithm are designed very efficient. For generating an initial solution, we develop an efficient constructive heuristic by modifying the best known NEH algorithm. Effectiveness of the proposed iterated greedy algorithm is tested on the Taillard 's instances. Computational results show the high efficiency of this algorithm with comparison state-of-the-art algorithms. We report new best solutions for 88 instances of 120 Taillard 's instances.
© 2012 IUST Publication, IJIEPR, Vol. 23, No. 4, All Rights Reserved.
1. Introduction
The flow shop scheduling problem is one of the most popular machine scheduling problems with extensive engineering relevance, representing nearly a quarter of manufacturing systems, assembly lines and information service facilities in use nowadays [1]. In the general flow shop model, it is assumed that the buffers have unlimited capacity. However, in many real flow shop environments, the buffers may have limited capacity due to technological requirements or process characteristics [2]. A special case of these environments is the flow shop with zero capacity buffers that the related problem is known as the
December 2012, Volume 23, Number 4
pp. 301-308
ISSN: 2008-4889
http://IJIEPR.iust.ac.ir/
An Iterated Greedy Algorithm for Solving the Blocking Flow Shop Scheduling Problem with Total Flow Time Criteria
D. Khorasanian & G. Moslehi*
Danial Khorasanian is an M.S. Student of Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran Ghasem Moslehi is a Professor of Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran
KEYWORDS
Constructive heuristic, Iterated greedy algorithm, Blocking flow shop, Total flow time
ABSTRACT
In this paper, we propose an iterated greedy algorithm for solving the blocking flow shop scheduling problem with total flow time minimization objective. The steps of this algorithm are designed very efficient. For generating an initial solution, we develop an efficient constructive heuristic by modifying the best known NEH algorithm. Effectiveness of the proposed iterated greedy algorithm is tested on the Taillard 's instances. Computational results show the high efficiency of this algorithm with comparison state-of-the-art algorithms. We report new best solutions for 88 instances of 120 Taillard 's instances.
© 2012 IUST Publication, IJIEPR, Vol. 23, No. 4, All Rights Reserved.
1. Introduction
The flow shop scheduling problem is one of the most popular machine scheduling problems with extensive engineering relevance, representing nearly a quarter of manufacturing systems, assembly lines and information service facilities in use nowadays [1]. In the general flow shop model, it is assumed that the buffers have unlimited capacity. However, in many real flow shop environments, the buffers may have limited capacity due to technological requirements or process characteristics [2]. A special case of these environments is the flow shop with zero capacity buffers that the related problem is known as the
References: [1] Wang, L., Pan, Q.K., Suganthan, P.N., Wang, W.H., & Wang, Y.M., "A Novel Hybrid Discrete Differential Evolution Algorithm for Blocking Flow Shop Scheduling Problems", Computers and Operations Research, Vol. 37, 2010, pp. 509-520. [2] Hall, N.G., Sriskandarajah, C., "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process", Operations Research, Vol. 44, 1996, pp. 510525. [3] Grabowski, J., Pempera, J., "The Permutation Flow Shop Problem with Blocking. A Tabu Search Approach", Omega, Vol. 35, 2007, pp. 302-311. [4] Grabowski, J., Pempera, J., "Sequencing of Jobs in Some Production System", European Journal of Operational Research, Vol. 125, 2000, pp. 535-550. [5] Rock, H., "Some New Results in Flow Shop Scheduling", Zeitschrift fur Operations Research, Vol. 28, 1984, pp. 116. [6] McCormick, S.T., Pinedo, M.L., Shenker, S., Wolf, B., "Sequencing in an Assembly Line with Blocking to Minimize Cycle Time", Operations Research, Vol. 37, 1989, pp. 925-935. [7] Ronconi, D.P., "A Note on Constructive Heuristics for the Flow Shop Problem with Blocking", International Journal of Production Economics, Vol. 87, 2004, pp. 39-48. International Journal of Industrial Engineering & Production Research, December 2012, Vol. 23, No. 4 D. Khorasanian & G. Moslehi An Iterated Greedy Algorithm for Solving the Blocking Flow Shop… 308 [8] Companys, R., Mateo, M., "Different Behaviour of a Double Branch-and-Bound Algorithm on Fm|Prmu|Cmax and Fm|Block|Cmax Problems", Computers and Operations Research, Vol. 34, 2007, pp. 938-953. [9] Wang, L., Pan, Q.K., Tasgetiren, M.F., "Minimizing the Total Flow Time in a Flow Shop with Blocking by using Hybrid Harmony Search Algorithms", Expert Systems with Applications, Vol. 37, 2010, pp. 7929-7936. [10] Nawaz, M., Enscore Jr, E.E., Ham, I., "A Heuristic Algorithm for the m-Machine, n-Job Flow-Shop Sequencing Problem", Omega, Vol. 11, 1983, pp. 91-95. [11] Caraffa, V., Ianes, S., Bagchi, T.P., Sriskandarajah, C., "Minimizing Makespan in a Blocking Flow Shop using Genetic Algorithms", International Journal of Production Economics, Vol. 70, 2001, pp. 101-115. [12] Ribas, I., Companys, R., Tort-Martorell, X., "An Iterated Greedy Algorithm for the Flow Shop Scheduling Problem with Blocking", Omega, Vol. 39, 2011, pp. 293-301. [13] Wang, L., Pan, Q.K., Tasgetiren, M.F., "A Hybrid Harmony Search Algorithm for the Blocking Permutation Flow Shop Scheduling Problem", Computers & Industrial Engineering, Vol. 61, 2011, pp. 76-83. [14] Ruiz, R., & Stutzle, T., "A Simple and Efective Iterated Greedy Algorithm for the Permutation Flow Shop Scheduling Problem", European Journal of Operational Research, Vol. 177, 2007, pp. 2033-2049. [15] Ronconi, D.P., Henriques, L.R.S., "Some Heuristic Algorithms for Total Tardiness Minimization in a Flowshop with Blocking", Omega, Vol. 37, 2009, pp. 272-281. [16] Framinan, J.M., Leisten, R., "An Eficient Constructive Heuristic for Flowtime Minimisation in Permutation Flow Shops", Omega, Vol. 31, 2003, pp. 311-317. [17] Kalczynski, P.J., Kamburowski, J., "An Improved NEH Heuristic to Minimize Makespan in Permutation Flow Shops", Computers and Operations Research, Vol. 35, 2008, pp. 3001-3008. [18] Taillard, E., "Benchmarks for Basic Scheduling Problems", European Journal of Operational Research, Vol. 64, 1993, pp. 278-285. International Journal of Industrial Engineering & Production Research, December 2012, Vol. 23, No. 4