Optimization of Multi Objective Job Shop Scheduling Problems Using Firefly Algorithm

Optimization of Multi Objective Job Shop Scheduling Problems Using Firefly Algorithm K.C. Udaiyakumar Sathyabama University M. Chandrasekaran Vels University

Scheduling is the allocation of resources over time to carry out a collection of tasks assigned in any field of engineering and non engineering. Majority of JSSP are categorized into non deterministic (NP) hard problem because of its complexity. Scheduling are generally solved by using heuristics to obtain optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using available resources in many cases. Many researchers attempted to solve the problem by applying various optimization techniques. While using traditional methods they observed huge difficulty in solving high complex problems and meta-heuristic algorithms were proved most efficient algorithms to solve various JSSP so far. The objective of this paper i) to make use of a newly developed meta heuristic called Firefly algorithm (FA) because of inspiration on Firefly and its characteristic. ii) To find the combined objective function by determining optimal make span, mean flow time and tardiness of different size problems (using Lawrence 1-40 problems) as a bench marking dataset and to find the actual computational time. Iii) to prove that the proposed FFA algorithm is a good problem solving technique for JSSP with multi criteria.
7 2014 157 162 https://www.scientific.net/PolicyAndEthics/PublishingPolicies https://www.scientific.net/license/TDM_Licenser.pdf 10.4028/www.scientific.net/AMM.591.157 https://www.scientific.net/AMM.591.157 https://www.scientific.net/AMM.591.157.pdf X.S. Yang, Nature-Inspired Metaheuristic Algorithms, Luniver Press, London, (2008). X. S. Yang, Firefly algorithms for multimodal optimization, Stochastic Algorithms: Foundations and Applications, SAGA, Lecture Notes in Computer Sciences 5792, 2009, p.169–178. 10.1007/978-3-642-04944-6_14 M.K. Sayadi, R. Ramezanian, and N. Ghaffari-Nasab, A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems, Int.J. Industrial Eng. Computations 1, 2010, p.1–10. 10.5267/j.ijiec.2010.01.001 C. Artigues and D. Feillet, A branch and bound method for the job-shop problem with sequence dependent setup times, Annals of Operations Research, 159, 2007, pp.135-159. 10.1007/s10479-007-0283-0 P. Baptiste, M. Flamini and F. Sourd, Lagrangian bounds for just-in-time job-shop scheduling, Computers & Operations Research, 35, 2008, pp.906-915. 10.1016/j.cor.2006.05.009 H. Gröflin and A. Klinkert. A new neighborhood and tabu search for the Blocking Job Shop, Discrete Applied Mathematics, 157, 2009, pp.3643-3655. 10.1016/j.dam.2009.02.020 R. Zhang and C. Wu, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Computers & operations Research, 38, 2011, pp.854-867. 10.1016/j.cor.2010.09.014 J. E. Beasley, OR-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1990, pp.1069-1072. 10.1038/sj/jors/0411109 K. Ripon, C. -H. Tsang and S. Kwong, An Evolutionary approach for solving the multi-objective job-shop scheduling problem, Studies in Computational Intelligence, 49, 2007, pp.165-195. 10.1007/978-3-540-48584-1_7 T. -L. Lin, S. -J. Horng, T. -W. Kao, Y. -H. Chen, R. -S. Run, R. -J. Chen, J. -L. Lai and I. H. Kuo, An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Systems with Applications, 37, 2010, pp.2629-2636. 10.1016/j.eswa.2009.08.015 10.1007/978-1-4615-5237-6 T.P. Bagchi, Multi Objective Scheduling by genetic Algorithms , , Kluwer Academic Publishers, (1999). M. Chandirasekaran and P. Ashokan, ' Multi Objective optimization of Job shop scheduling usingsheep flocks Heredity Model Algorithm, Internation Journal of Manufacturing Sceince and echnology, USA, Vol 9, No 2, 2007, pp.47-54. Aphirak Khadwilard1 et all, Investigation of Firefly Algorithm Parameter Setting for Solving Job Shop Scheduling Problems, Operation Research Network, Thailand, vol 2554, 2012, pp.89-97. José Fernando Gonçalves, Jorge José de Magalhães Mendes and Maurício G.C. Resende, A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem, AT&T Labs Research Technical Report TD 5EAL6J, (2002). 10.1016/j.ejor.2004.03.012