Flow shop scheduling decisions through Techniques for Order Preference by Similarity to an Ideal Solution (TOPSIS)

Arun Gupta, Shailendra Kumar


The flow-shop scheduling problem (FSP) has been widely studied in the literature and having a very active research area. Over the last few decades, a number of heuristic/meta-heuristic solution techniques have been developed. Some of these techniques offer excellent effectiveness and efficiency at the expense of substantial implementation efforts and being extremely complicated. This paper brings out the application of a Multi-Criteria Decision Making (MCDM) method known as techniques for order preference by similarity to an ideal solution (TOPSIS) using different weighting schemes in flow-shop environment. The objective function is identification of a job sequence which in turn would have minimum makespan (total job completion time). The application of the proposed method to flow shop scheduling is presented and explained with a numerical example. The results of the proposed TOPSIS based technique of FSP are also compared on the basis of some benchmark problems and found compatible with the results obtained from other standard procedures.


Scheduling; Multi-Criteria Decision Making; TOPSIS; flow-shop

Full Text:



Albadawi, Z., Bashir, H.A., Chen, M. (2005). A mathematical approach for the formation of manufacturing cells. Computers & Industrial Engineering, 48(1): 3–21. http://dx.doi.org/10.1016/j.cie.2004.06.008

Aldowaisan, T., Allahvedi, A. (2003), New heuristics for no-wait flowshops to minimize makespan. Computers & Operations Research, 30(8): 1219–31. http://dx.doi.org/10.1016/S0305-0548(02)00068-0

Behzadian, M., Otaghsara, S., Yazdani, M., Ignatius, J. (2012). A state-of the-art survey of TOPSIS applications. Expert Systems with Applications, 39(17), 13051-13069. http://dx.doi.org/10.1016/j.eswa.2012.05.056

Blum, C., Roli, A. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308. http://dx.doi.org/10.1145/937503.937505

Campbell, H.G., Dudek, R.A., Smith, M.L. (1970). A heuristic algorithm for the n-job, m-machine problem. Management Science, 16(10), B630–7. http://dx.doi.org/10.1287/mnsc.16.10.B630

Carlier, J. (1978). Ordonnancements a contraintes disjonctives, R.A.I.R.O. Recherche operationelle/Operations Research, 12(4), 333-351.

Chen, C-L., Vempati, V.S., Aljaber, N. (1995). An application of genetic algorithms for flow shop problems. European Journal of Operational Research, 80(2), 389-396. http://dx.doi.org/10.1016/0377-2217(93)E0228-P

Cheung, W.M., Zhou, H. (2001). Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Annals of Operations Research, 107(1), 65–81. http://dx.doi.org/10.1023/A:1014990729837

Dannenbring, D.G. (1977). An evaluation of flow-shop sequencing heuristic. Management Science, 23(11), 1174–1182. http://dx.doi.org/10.1287/mnsc.23.11.1174

Davoud Pour, H. (2001). A new heuristic for the n-job, m-machine flow-shop problem. Production Planning and Control, 12(7), 648–53. http://dx.doi.org/10.1080/09537280152582995

Fink, A., Vob, S. (2003). Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research,151(2), 400–414. http://dx.doi.org/10.1016/S0377-2217(02)00834-2

French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Limited.

Garey, M.R.D., Johnson, D.S., Sethi, R. (1976). The complexity of flow shop and job shop scheduling. Mathematics of Operations Research, 1, 117-29. http://dx.doi.org/10.1287/moor.1.2.117

Gonzalez, T., Sahni, S. (1978). Flow shop and job shop schedules. Operations Research, 26, 36–52. http://dx.doi.org/10.1287/opre.26.1.36

Grabowski, J., Wodecki, M. (2004). A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Computers and Operations Research, 31(11), 1891–909. http://dx.doi.org/10.1016/S0305-0548(03)00145-X

Guinet, A., Legrand, M. (1998). Reduction of job-shop problems to flow-shop problems with precedence constraints. European Journal of Operational Research, 109(1), 96–110. http://dx.doi.org/10.1016/S0377-2217(97)00129-X

Gupta, A., Chauhan, S. (2015). A heuristic algorithm for scheduling in a flow shop environment to minimize makespan. International Journal of Industrial Engineering Computations, 6(2), 173-184. http://dx.doi.org/10.5267/j.ijiec.2014.12.002

Hejazi, S.R., Saghafian, S. (2005). Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895–2929. http://dx.doi.org/10.1080/0020754050056417

Johnson, S.M. (1954). Optimal two and three-stage production schedules with set-up times included. Naval Research Logistics Quarterly, 1(1), 61-68. http://dx.doi.org/10.1002/nav.3800010110

King, J.R., Spachis, A.S. (1980). Heuristics for flowshop scheduling. International Journal of Production Research, 18(3), 343–357. http://dx.doi.org/10.1080/00207548008919673

Koulamas, C. (1998). A new constructive heuristic for the flowshop scheduling problem. European Journal of Operational Research; 105(1), 66–71. http://dx.doi.org/10.1016/S0377-2217(97)00027-1

Kumar, S., Sharma, R.K. (2014). Cell formation heuristic procedure considering production data. International Journal of Production Management and Engineering, 2(2), 75–84. http://dx.doi.org/10.4995/ijpme.2014.2078

Kumar, S., Sharma, R.K. (2015). Development of a cell formation heuristic by considering realistic data using principal component analysis and Taguchi’s method. Journal of Industrial Engineering International, 11(1), 87-100.http://dx.doi.org/10.1007/s40092-014-0093-3

Laha, D., Chakraborty, U.K. (2009). An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 44(5), 559–569. http://dx.doi.org/10.1007/s00170-008-1845-2

Nakhaeinejad, M., Nahavandi, N. (2012). An interactive algorithm for multi-objective flow shop scheduling with fuzzy processing time through resolution method and TOPSIS. International Journal of Advanced Manufacturing Technology, 66(5), 1047-1064. http://dx.doi.org/10.1007/s00170-012-4388-5

Nawaz, M., Enscore, Jr. E., Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, InternationalJournal of Management Science, 11, 91–95.

Nowicki, E., Smutnicki, C. (1996). A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91(1), 160–75. http://dx.doi.org/10.1016/0377-2217(95)00037-2

Ogbu, F.A., Smith, D.K. (1990). The application of the simulated annealing algorithms to the solution of the n/m/Cmax flowshop problem. Computers & Operations Research, 17(3), 243–53. http://dx.doi.org/10.1016/0305-0548(90)90001-N

Olson, D.L. (2004). Comparison of weights in TOPSIS models. Mathematical and Computer Modeling, 40(7-8), 721–727. http://dx.doi.org/10.1016/j.mcm.2004.10.003

Osman, I.H., Potts, C.N. (1989). Simulated annealing for permutation flow-shop scheduling. Omega, The International Journal of Management Science, 17(6), 551–7.

Palmer, D.S. (1965). Sequencing jobs through a multistage process in the minimum total time: a quick method of obtaining a near optimum. Operations Research Quarterly, 16(1), 101–7. http://dx.doi.org/10.1057/jors.1965.8

Rajendran, C., Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426–38. http://dx.doi.org/10.1016/S0377-2217(02)00908-6

Reeves, C.R. (1993). Improving the efficiency of tabu search for machine scheduling problems. Journal of the Operational Research Society, 44(4), 375–82. http://dx.doi.org/10.2307/2584415

Reeves, C.R., (1995). A genetic algorithm for flowshop sequencing. Computers and Operations Research 22(1), 5–13. http://dx.doi.org/10.1016/0305-0548(93)E0014-K

Ruiz, R., Maroto, C., Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, International Journal of Management Science, 34, 461–76. http://dx.doi.org/10.1016/j.omega.2004.12.006

Ruiz, R., Stutzle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049. http://dx.doi.org/10.1016/j.ejor.2005.12.009

Ruiz, R., Maroto, C. (2005). A comprehensive review and evaluation of permutation flow shop heuristics. European Journal of Operational Research, 165(2), 479–494. http://dx.doi.org/10.1016/j.ejor.2004.04.017

Sarraf, A.Z., Mohaghar, A., Bazargani, H. (2013). Developing TOPSIS method using statistical normalization for selecting Knowledge management strategies. Journal of Industrial Engineering and Management, 6(4), 860-875. http://dx.doi.org/10.3926/jiem.573

Schuster, C.J., Framinan, J.M. (2003). Approximate procedures for no wait job shop scheduling. Operations Research Letters, 31(4), 308–318. http://dx.doi.org/10.1016/S0167-6377(03)00005-1

Shih, H.S, Syur, H.J., Lee, E.S. (2007). An extension of TOPSIS for group decision making. Mathematical and Computer Modeling, 45(7-8), 801-813. http://dx.doi.org/10.1016/j.mcm.2006.03.023

Stützle, T. (1998). Applying iterated local search to the permutation flowshop problem. Technical Report, AIDA-98-04, TU Darmstadt, FG Intellektik;

Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research,47(1), 65–74. http://dx.doi.org/10.1016/0377-2217(90)90090-X

Turner, S., Booth, D., (1987). Comparison of heuristics for flow shop sequencing. OMEGA, The International Journal of Management Science15(1), 75–78. http://dx.doi.org/10.1016/0305-0483(87)90054-5

Vega, A., Aguaron, J., García-Alcaraz, J., Moreno-Jiménez, J.M. (2014). Notes on Dependent Attributes in TOPSIS. Procedia Computer Science, 31, 308 – 317. http://dx.doi.org/10.1016/j.procs.2014.05.273

Wang, L., Zheng, D. (2001). An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research,28(6), 585–596. http://dx.doi.org/10.1016/S0305-0548(99)00137-9

Wang, L., Zheng, D.Z. (2003). An effective hybrid heuristic for flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 21(1), 38–44. http://dx.doi.org/10.1007/s001700300005

Werner, F. (1993). On the heuristic solution of the permutation flow shop problem by path algorithms. Computers and Operations Research20(7), 707–722. http://dx.doi.org/10.1016/0305-0548(93)90058-Q

Widmer M, Hertz A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41(2), 186–93. http://dx.doi.org/10.1016/0377-2217(89)90383-4

Yoon, K., Hwang, C.L. (1980). Multiple Attribute Decision Making Methods and Applications. A State of the Art Survey. Berlin: Springer Verlag.

Zobolas, G.I., Tarantilis, C.D., Ioannou, G. (2009). Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research 36(4), 1249-1267. http://dx.doi.org/10.1016/j.cor.2008.01.00

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317