International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 7, No. 4, 8 Mar. 2015
Cover page and Table of Contents: PDF (size: 321KB)
Hybrid Multi-Objective Particle Swarm Optimization for Flexible Job Shop Scheduling Problem
Full Text (PDF, 321KB), PP.54-61
Views: 0 Downloads: 0
Author(s)
S. V. Kamble
1,*
S. U. Mane
1
A. J. Umbarkar
2
Index Terms
Particle Swarm Optimization, Simulated Annealing, Multi Objective Optimization, Job Shop Scheduling, Metaheurestic
Abstract
Hybrid algorithm based on Particle Swarm Optimization (PSO) and Simulated annealing (SA) is proposed, to solve Flexible Job Shop Scheduling with five objectives to be minimized simultaneously: makespan, maximal machine workload, total workload, machine idle time & total tardiness. Rescheduling strategy used to shuffle workload once the machine breakdown takes place in proposed algorithm. The hybrid algorithm combines the high global search efficiency of PSO with the powerful ability to avoid being trapped in local minimum of SA. A hybrid multi-objective PSO (MPSO) and SA algorithm is proposed to identify an approximation of the pareto front for Flexible job shop scheduling (FJSSP). Pareto front and crowding distance is used for identify the fitness of particle. MPSO is significant to global search and SA used to local search. The proposed MPSO algorithm is experimentally applied on two benchmark data set. The result shows that the proposed algorithm is better in term quality of non-dominated solution compared to the other algorithms in the literature.
Cite This Paper
S. V. Kamble, S. U. Mane, A. J. Umbarkar, "Hybrid Multi-Objective Particle Swarm Optimization for Flexible Job Shop Scheduling Problem", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.4, pp.54-61, 2015. DOI:10.5815/ijisa.2015.04.08
Reference
[1]P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu Search,” Annals of Oper. Res., 1993, Vol. 41, pp. 157-183.
[2]J Paulli, “A hierarchical approach for the FMS scheduling problem,” Eur J. Oper. Res., 1995, Vol. 86(1), pp. 32–42.
[3]J. Hurink , B. Jurisch and M. Thole, “Tabu search for the job-shop scheduling with multi-purpose machines,” OR Spektrum, 1994, Vol. 15, pp.205-215.
[4]S. Dauzere-Peres, J. Paulli, “An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem with tabu search,” Annals of Oper. Res., 1997, Vol. 70, pp. 281-306.
[5]J. Chen, K Chen, J. Wu, and C.Chen, “A study of the flexible job shop scheduling problem with parallel machines and reentrant process,” Int J. Adv Manuf. Technol., 2008, 39(3), pp. 344–354.
[6]M. Mastrolilli, L.M. Gamberdella, “Effective neighborhood for the flexible job shop problem,” J. of Scheduling, 2000, Vol. 3, no.1, pp. 3-20.
[7]D.Y. Sha, Lin Hsing-Hung, “A multi-objective PSO for job-shop scheduling problems,” Expert Systems with Applications 37, 2010, pp. 1065–1070.
[8]Xia, Z.Wu, “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems,” Computer Ind. Eng. 48(2), 2005, pp. 409–425.
[9]I. Kacem, Hammadi, and P. Borne, “Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic,” Math Comput. Simul. 60(3–5), 2002, pp. 245–276,
[10]J.Gao, L.Sun, and M.Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Comput. Oper. Res. 35(9), 2008, pp. 2892–2907.
[11]Li Jun-qing, and Yu-xia Pan, “A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling problem,” Int. J. Adv Manuf Technol. 66, 2013, pp. 583–596.
[12]R.Tavakkoli-Moghaddam, M.Azarkish and A.Sadeghnejad-Barkousaraie, “A hybrid algorithm based on particle swarm optimization and simulated annealing for periodic job shop scheduling problem,” Expert Systems with Applications 38, 20011, pp. 10812–10821.
[13]Zhang Guohui, Shao Xinyu, “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem,” Computers & Industrial Engineering 56, 2009, pp.1309–1318.
[14]P.Fattahi, M. Manesh, and A. Roshani, “A new solution seed for job shop scheduling problem,” Appl. Mech. Mater 110–116, 2012, pp. 3899–3905.
[15]R.Carlo, C.Raquel, Jr. Prospero Naval, “An Effective Use of Crowding Distance in Multi-objective Particle Swarm Optimization,” IEEE Processding,2008
[16]D.Lei, “A Pareto archive particle swarm optimization for multi-objective job shop scheduling,” Comput Ind. Eng. 54(4), 2008, pp. 960–971.
[17]A.Bagheri, Zandiesh, “An artificial immune algorithm for the flexible job shop scheduling problem,” Futur Gener. Compter Sys 26(4), 2010, pp. 533-541.
[18]Shao Xinyu, Weiqi Liu, Liu Qiong, Zhang Chaoyong, “Hybrid discrete particle swarm optimization for multi-objective flexible job shop scheduling problem,” Int. J. Adv Manuf Tech., 2013, pp. 2885–2901.
[19]G.Zhang, X. Shao, P.Li, and Gao, “An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem,” Computer Ind. Eng 56(4), 2009, pp. 1309–1318.
[20]J.Kennedy, R. Eberhart, “Particle swarm optimization,” Proc IEEE Int. Conf. Neural Network 194, 1995, pp 1942–1948.
[21]Wang Hui-Mei, Fuh-Der Chou, and Ful-Chiang Wu, “A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan,” Int. J. Adv. Manuf Technol., 2011, pp. 761–776.
[22]Li. Xing Ning , Wu Ying, Chen, Ke-Wei Yang, “ An efficient search method for multi-objective flexible job shop scheduling problems,” J. Intell Manuf, 2009, pp. 283–293.
[23]H.Chen, J. Ihlow, C. Lehmann, “A genetic algorithm for flexible job shop scheduling problem,” In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1120–1125.
[24]Zhang Liping, Gao Liang, Li Xinku, “A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problem with disruptions,” Int. J. Adv. Manfuc. Tech., 2013, pp. 1141-1156.
[25]H.Wei ,D. Dun, “ Scheduling flexible job shop problem subject to machine breakdown with route changing and right shift strategies,” Int. J. Adv. Manf. Tech., 2013, pp. 501-514.
[26]P.R.Dian and M.S.Siti, “Particle Swarm Optimization: Technique, System & challenges,” Int. J. Comp. App. (0975-8887), 2011.
[27]L.N.Xing, Y.Chen, K.W. Yang, “An efficient search method for multi-objective flexible job shop scheduling problems,” J. Intell. Manuf., 2009, pp: 283-293. 2013.
[28]Sudip Kumar Sahana, Aruna Jain, Prabhat Kumar Mahanti, “Ant Colony Optimization for Train Scheduling: An Analysis,” Int.J. Intelligent Systems and Applications, 2014, 02, 29-36.
[29]Mustapha Guezouri, Abdelkrim Houacin, “ Hybrid Flow Shop Scheduling Problem Using Artificial Immune System,” Int. J. Intelligent Systems and Applications, 2012, 10, 82-88.