A New GT Heuristic for Solving Multi Objective Job Shop Scheduling Problems

A New GT Heuristic for Solving Multi Objective Job Shop Scheduling Problems D. Lakshmipathy Vels University M. Chandrasekaran Vels University T. Balamurugan St.Joesph’s College of Engineering P. Sriramya Saveetha School of Engineering

The n-job, m-machine Job shop scheduling (JSP) problem is one of the general production scheduling problems in manufacturing system. Scheduling problems vary widely according to specific production tasks but most are NP-hard problems. Scheduling problems are usually solved using heuristics to get optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using reasonable resources in many cases. In this paper, optimization of three practical performance measures mean job flow time, mean job tardiness and makespan are considered. New Game theory based heuristic method (GT) is used for finding optimal makespan, mean flow time, mean tardiness values of different size problems. The results show that the GT Heuristic is an efficient and effective method that gives better results than Genetic Algorithm (GA). The proposed GT Heuristic is a good problem-solving technique for job shop scheduling problem with multi criteria.
7 2014 184 188 https://www.scientific.net/PolicyAndEthics/PublishingPolicies https://www.scientific.net/license/TDM_Licenser.pdf 10.4028/www.scientific.net/AMM.591.184 https://www.scientific.net/AMM.591.184 https://www.scientific.net/AMM.591.184.pdf 10.1007/978-3-662-03088-2 Bruker, P., Scheduling Algorithms 2nd Edn, Springer-Verlag, Berlin (1995). 10.1287/moor.1.2.117 Garey, M., et al., The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, (1976) pp.117-129. Erschler J.F., Roubellat J.P., Vernhes., Finding some essential characteristics of the feasible solutions for a scheduling problem. Operations Research, 24, (1976) pp.774-783. 10.1287/opre.24.4.774 French, S., Sequencing and scheduling: An introduction to the mathematics of the job shop, New York, Wiley (1982). 10.1007/978-3-662-11712-5 Mattfeld, D.C., Evolutionary Search and the Job Shop, Physica-Verlag, (1996). Ono, I., Yamamura, M., and Kobayashi, S., A genetic algorithm for job-shop scheduling problems using job-based order crossover, In Proceedings of ICEC '96, (1996), pp.547-552. 10.1109/icec.1996.542658 10.1007/978-1-4615-5237-6 Bagchi, T.P., Multiobjective Scheduling By Genetic Algorithms, Kluwer Academic Publishers, (1999). Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, (2001). Garen, J., Multi objective Job-Shop Scheduling with Genetic Algorithms Using a New Representation and Standard Uniform Crossover, MH Workshop, (2003).