Abstract
Many optimization problems from the industrial engineering world, in particular manufacturing systems, are very complex in nature and are quite hard to solve by conventional optimization techniques. There has been increasing interest to apply metaheuristic methods to solve such kinds of hard optimization problems. In this work, a novel metaheuristic approach called scatter search (SS) is applied for the n/m/P/C max problem, an NP-hard sequencing problem, which is used to find a processing order of n different jobs to be processed on m machines in the same sequence with minimizing the makespan. SS contrasts with other evolutionary procedures by providing a wide exploration of the search space through intensification and diversification. In addition, it has a unifying principle for joining solutions and they exploit the adaptive memory principle to avoid generating or incorporating duplicate solutions at various stages of the problem. In this paper, various metaheuristic methods and best heuristics from the literature are used for solving the well-known benchmark problem set of Taillard (Eur J Oper Res 64:278–285, 1993). The results available for the various existing metaheuristic and heuristic methods are compared with the results obtained by the SS method. The proposed framework achieves better results for 4 of 12 benchmark problems and also achieves an average deviation of 1.003% from the benchmark problem set of Taillard (Eur J Oper Res 64:278–285, 1993). The computational results show that SS is a more effective metaheuristic for the n/m/P/C max problem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Control Cybern 29(3):653–684
Widmer M, Hertz A (1989) A new heuristic method for the flow shop sequencing problem. Eur J Oper Res 41(2):186–193
Pinedo M (1995) Scheduling: theory, algorithm, and systems. Prentice-Hall, Englewood Cliffs, New Jersey
Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist Q 1(1):61–68
Lomnicki ZA (1965) A “branch-and-bound” algorithm for the exact solution of the three-machine scheduling problem. Oper Res Q 16(1):89–100
Osman IH, Potts CN (1989) Simulated annealing for permutation flow-shop scheduling. OMEGA Int J Manag Sci 17(6):551–557
Palmer DS (1965) Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Oper Res Q 16(1):101–107
Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n-job, m-machine sequencing problem. Manage Sci 16(10):630–637
Gupta JND (1971) A functional heuristic algorithm for the flowshop scheduling problem. Oper Res Q 22(1):39–47
Dannenbring DG (1977) An evaluation of flow shop sequencing heuristics. Manage Sci 23(11):1174–1182
Rock H, Schmidt G (1982) Machine aggregation heuristics in shop scheduling. Methods Oper Res 45:303–314
Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA Int J Manag Sci 11(1):91–95
Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. OMEGA Int J Manag Sci 15(1):75–78
Taillard E (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47(1):65–74
Ho JC, Chang Y-L (1990) A new heuristic for the n-job, m-machine flow shop problem. Eur J Oper Res 52(2):194–206
Ogbu FA, Smith DK (1990) The application of the simulated annealing algorithm to the solution of the n/m/C max flow shop problem. Comput Oper Res 17(3):243–253
Nowicki E, Smutnicki C (1996) A fast tabu search algorithm for the permutation flow-shop problem. Eur J Oper Res 91(1):160–175
Ben-Daya M, Al-Fawzan M (1998) A tabu search approach for the flow shop scheduling problem. Eur J Oper Res 109(1):88–95
Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, Massachusetts
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, Michigan
van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. D. Reidel, Dordrecht, The Netherlands
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculation by fast computing machine. J Chem Phys 21(6):1087–1092
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston, Massachusetts
Nowicki E, Smutnicki C (2006) Some aspects of scatter search in the flow-shop problem. Eur J Oper Res 169(2):654–666
Stutzle T (1998) Applying iterated local search to the permutation flow shop problem. Technical report, AIDA-98-04, FG Intellektik, TU Darmstadt, Germany
Ruiz R, Maroto C (2005) A comprehensive review and evaluation of permutation flowshop heuristics. Eur J Oper Res 165(2):479–494
Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285
Chen C-L, Vempati VS, Aljaber N (1995) An application of genetic algorithms for flow shop problems. Eur J Oper Res 80(2):389–396
Reeves C, Yamada T (1998) Genetic algorithms, path relinking, and the flowshop sequencing problem. Evol Comput 6(1):230–234
Murata T, Ishibuchi H, Tanaka H (1996) Genetic algorithms for flowshop scheduling problems. Comput Ind Eng 30(4):1061–1071
Ponnambalam SG, Aravindan P, Chandrasekaran S (2001) Constructive and improvement flow shop scheduling heuristics: an extensive evaluation. Prod Plan Control 12(4):335–344
Reza Hejazi S, Saghafian S (2005) Flowshop-scheduling problems with makespan criterion: a review. Int J Prod Res 43(14):2895–2929
Noorul Haq A, Saravanan M, Vivekraj AR, Prasad T (2007) A scatter search approach for general flowshop scheduling problem. Int J Adv Manuf Technol 31(7–8):731–736
Colin RR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22(1):5–13
Glover F (1998) A template for scatter search and path relinking. In: Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Lecture notes in computer science, vol 1363, pp 13–54 (expanded version available on request)
Martí R, Laguna M, Campos V (2005) Scatter search vs. genetic algorithms: an experimental evaluation with permutation problems. In: Rego C, Alidaee B (eds) Metaheuristic optimization via adaptive memory and evolution: tabu search and scatter search. Kluwer Academic Publishers, Norwell, Massachusetts, pp 263–282
Ying K-C, Liao C-J (2004) An ant colony system for permutation flow-shop sequencing. Comput Oper Res 31(5):791–801
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saravanan, M., Noorul Haq, A., Vivekraj, A.R. et al. Performance evaluation of the scatter search method for permutation flowshop sequencing problems. Int J Adv Manuf Technol 37, 1200–1208 (2008). https://doi.org/10.1007/s00170-007-1053-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-007-1053-5