Abstract
Due to intense competition in the market place, effective scheduling has now become an important issue for the growth and survival of manufacturing firms. To sustain in the current competitive environment, it is essential for the manufacturing firms to improve the schedule based on simultaneous optimization of performance measures such as makespan, flow time, and tardiness. The current paper presents a novel particle swarm optimization (PSO) algorithm for solving multi-objective flexible job shop scheduling problem with the goal of finding approximations of the optimal Pareto front. The Pareto-optimal solutions obtained through multi-objective particle swarm optimization (MOPSO) have been ranked by the composite scores obtained through maximum deviation theory (MDT) to avoid subjectiveness and impreciseness in the decision-making. The results are compared with non-dominated sorting genetic algorithm-II (NSGA-II) and multi-objective evolutionary algorithm (MOEA) in terms of four performance metrics. Twenty-eight benchmark instances from literature are solved by the proposed algorithm. It is observed that MOPSO outperforms NSGA-II and MOEA in four performance metrics in most of the instances.
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
Garey EL, Johnson DS, Sethi R (1976) The Complexity of flow-shop and job-shop scheduling. Math Oper Res 1(2):117–129
Xia WJ, Wu ZM (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48(2):409–425
Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54(3):453–473
Li JQ, Pan QK, Liang YC (2010) An effective hybrid tabu search algorithm for multi-objective flexible job shop scheduling problems. Comput Ind Eng 59(4):647–662
Kacem I, Hammadi S, Borne P (2002) Pareto-optimality approach for flexible job-shop scheduling problems, hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60(3–5):245–276
Frutos M, Olivera AC, Tohme F (2010) A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem. Ann Oper Res 181(1):745–765
Wang X, Gao L, Zhang C, Shao X (2010) A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Technol 51(5–8):757–767
Moslehi G, Mahnam MA (2011) Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. Int J Prod Econ 129(1):14–22
Li JQ, Pan QK, Tasgetiren MF (2014) A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 38(3):1111–1132
Rabiee M, Zandieh M, Ramezani P (2012) Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches. Int J Prod Res 50(24):7327–7342
Li JQ, Pan QK, Chen J (2012) A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems. Int J Prod Res 50(4):1063–1078
Singh MR, Mahapatra SS (2011) A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. Int J Adv Manuf Technol 62(1–4):267–277
Wang YM (1998) Using the method of maximizing deviations to make decision for multi-indices. Syst Eng Electron 20(7):24–26
Brandimarte P (1993) Routing and scheduling in a flexible jobshop by tabu search. Ann Oper Res 41(3):157–183
Perez MAF, Raupp FM (2014) A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem. J Intell Manuf. doi:10.1007/s10845-014-0872-0
Xing LN, Chen YW, Wang P, Zhao QS, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl Soft Comput 10(3):888–896
Bagheri A, Zandieh M, Mahdavi I, Yazdani M (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Futur Gener Comput Syst 26(4):533–541
Chang PC, Hsieh JC, Lin SG (2002) The development of gradual-priority weighting approach for the multi-objective flow-shop scheduling problem. Int J Prod Econ 79(3):171–183
Suresh R, Mohanasundaram KM (2006) Pareto archived simulated annealing for job shop scheduling with multiple objectives. Int J Adv Manuf Technol 29(1–2):184–196
Coello CA, Plido GT, Lechga MS (2004) Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Comput 8(3):256–278
Lei D (2008) A Pareto archive particle swarm optimization for multi-objective job shop scheduling. Comput Ind Eng 54(4):960–971
Lei D, Wu Z (2006) Crowding measure-based multiobjective evolutionary algorithm for job shop scheduling. Int J Adv Manuf Technol 30(1–2):112–117
Kennedy J, Eberhart R (1995) Particle swarm optimization. Proceedings of IEEE International Conference on Neural Network, Washington, USA, November/December 4:1942–1948
Yoshida H, Kawata K, Fukuyama Y, Nakanishi YA (2001) Particle swarm optimization for reactive power and voltage control considering voltage security assessment. IEEE Trans Power Syst 15(4):1232–1239
Brandstatter B, Baumgartner U (2002) Particle swarm optimization mass-spring system analogon. IEEE Trans Magn 38(2):997–1000
Belmecheri F, Prins C, Yalaoui F, Amodeo L (2013) Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. J Intell Manuf 24(4):775–789
Basu M (2008) Dynamic economic emission dispatch using nondominated sorting genetic algorithm-II. Int J Electr Power Energy Syst 30(2):140–149
Kim B, Son S (2012) A probability matrix based particle swarm optimization for the capacitated vehicle routing problem. J Intell Manuf 23(4):1119–1126
Mostaghim S, Teich J (2003) Strategies for finding good local guides in multi-objective particle swarm optimization. Proceedings of the IEEE Symposium on Swarm Intelligence. 26–33
Wang LF, Singh C (2007) Environmental/economic power dispatch using a fuzzified multiobjective particle swarm optimization algorithm. Electr Power Syst Res 77(12):1654–1664
Li X (2004) Better spread and convergence: particle swarm multiobjective optimization using the maximin fitness. Lect Notes Comput Sci Genet Evol Comput - GECCO 3102:117–128
Raquel CR, Naval PC (2005) An effective use of crowding distance in multiobjective particle swarm optimization. Proceedings of Conference on Genetic and Evolutionary Computation (GECCO '05), New York, USA. 257–264
Alvarez-Benitez JE, Everson RM, Fieldsend JE (2005) A MOPSO algorithm based exclusively on pareto dominance concepts. Evol Multi-Criterion Optim Lect Notes Comput Sci 3410:459–473
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Ebrahimipour V, Haeri A, Sheikhalishahi M, Asadzadeh SM (2012) Application of multi-objective particle swarm optimization to solve a fuzzy multi-objective reliability redundancy allocation problem. J Saf Eng 1(2):26–38
Pant M, Radha T, Singh VP (2007) A simple diversity guided particle swarm optimization. Proceedings of IEEE Congress on Evolutionary Computation (CEC), 25–28 September, Singapore, pp. 3294–3299
Dauzere-Peres S, Paulli EJ (1997) An integrated approach for modeling and solving the general multi-processor job shop scheduling problem using tabu search. Ann Oper Res 70:281–306
Bachlaus M, Pandey MK, Mahajan C, Shankar R, Tiwari MK (2008) Designing an integrated multi-echelon agile supply chain network: a hybrid taguchi-particle swarm optimization approach. J Intell Manuf 19(6):747–761
Modares H, Alfi A, Sistani MBN (2011) Parameter estimation of bilinear systems based on an adaptive particle swarm optimization. Eng Appl Artif Intell 23(7):1105–1111
Rahmati SHA, Zandieh M, Yazdani M (2013) Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem. Int J Adv Manuf Technol 64(5–8):915–932
Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: Methods and applications. Doctoral dissertation ETH 13398, Swiss Federal Institute of Technology (ETH). Zurich, Switzerland
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Singh, M.R., Singh, M., Mahapatra, S.S. et al. Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem. Int J Adv Manuf Technol 85, 2353–2366 (2016). https://doi.org/10.1007/s00170-015-8075-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-015-8075-1