A Tabu Search Approach for Permutation Flow Shop Scheduling

  • C.E. Dodu Technical University of Cluj-Napoca, Department of Manufacturing Engineering, B-dul Muncii 103-105, 400641 Cluj-Napoca, Romania
  • M. Ancău Technical University of Cluj-Napoca, Department of Manufacturing Engineering, B-dul Muncii 103-105, 400641 Cluj-Napoca, Romania

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

[1] A.Agarwal, S.Colak, and E.Eryarsoy. Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach. European Journal of Operational Research 169 (2006), 801–815.
[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.
Published
2020-07-13
How to Cite
DODU, C.E.; ANCĂU, M.. A Tabu Search Approach for Permutation Flow Shop Scheduling. Studia Universitatis Babeș-Bolyai Informatica, [S.l.], v. 65, n. 1, p. 104-115, july 2020. ISSN 2065-9601. Available at: <http://www.cs.ubbcluj.ro/~studia-i/journal/journal/article/view/54>. Date accessed: 04 dec. 2020. doi: https://doi.org/10.24193/subbi.2020.1.08.
Section
Articles