A Tabu Search Approach for Permutation Flow Shop Scheduling
Abstract
The adaptive distance between the neighbourhood’s makespans influences the local search to explore the non-investigated areas of the solutions space. A Tabu Search with the intensive concentric exploration over non-explored areas is proposed as an alternative solution to the simplest Tabu Search with the random shifting of two jobs indexes operation for Permutation Flow Shop Problem (PFSP) with the makespan minimization criteria.
References
[2] Baker, K. R. Introduction to sequencing and scheduling.
[3] C.R.Reeves, and T.Yamada. Genetic algorithms, path relinking and the flowshop sequencing problem. Evol Comput 16 (1998), 230–234.
[4] D.G.Dannenbring. An evaluation of flow-shop sequence heuristics. Management Science 23 (1977), 1174–1182.
[5] D.S.Palmer. Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near-optimum. Operational Research Quarterly 16 (1965), 101–107.
[6] E.Nowicki, and C.Smutnicki. A fast tabu search algorithm for the permutation flowshop problem. European Journal of Operational Research 91 (1996), 160–175.
[7] E.Taillard. Some efficient heuristic methods for the flow-shop sequencing problem. European Journal of Operational Research 6 (1990), 65–74.
[8] E.Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research 64 (1993), 278–285.
[9] F.Glover. Tabu search-part i. ORSA Journal on Computing 1, 3 (1989), 190–206.
[10] G.Ochoa, and N.Veerapen. Deconstructing the big valley search space hypothesis. In Evolutionary Computation in Combinatorial Optimization (2016), F. Chicano, B. Hu, and P. Garc´ıa-S´anchez, Eds., Springer International Publishing, pp. 58–73.
[11] H.G.Campbell, R.A.Dudek, and M.L.Smith. A heuristic algorithm for the n-job, m-machine, sequencing problem. Management Science 6 (1970), 630–637.
[12] J.N.D.Gupta. A functional heuristic for the flow-shop scheduling problem. Operational Research Quarterly 22 (1971), 39–47.
[13] M.Eskenasi, and M.Mehrandezh. The permutation flow-shop scheduling using a genetic algorithm-based iterative method. Industrial Engineering and Management (2016).
[14] M.Nawaz, E.Enscore, and I.Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA 11 (1983), 91–95.
[15] M.R.Garey, D.S.Johnson, and R.Sethi. The complexity of flowshop and job shop scheduling. Mathematics of Operations Research 1 (2016), 117–129.
[16] R.A.Gupta, and S.Chauhan. A heuristic algorithm for scheduling in a flow shop environment to minimize makespan. International Journal of Industrial Engineering Computations 6 (2015), 173–184.
[17] S.M.Johnson. Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1 (1954), 61–68.
[18] Z.A.Drezner. New heuristic for the quadratic assignment problem. Journal of Applied Mathematics and Decision Sciences 6 (2002), 163–173.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Transfer of copyright agreement: When the article is accepted for publication, I, as the author and the representative of the coauthors, hereby agree to transfer to Studia Universitatis Babes-Bolyai, Series Informatica, all rights, including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the authors specifically retain: the authors can use the material however they want as long as it fits the NC ND terms of the license. The authors have all rights for reuse according to the below license.