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

Abstract:

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.

• Periodical: Applied Mechanics and Materials (Volume 591)
• Pages: 184-188
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.591.184
• Online since: July 2014
• Authors: D. Lakshmipathy*, M. Chandrasekaran, T. Balamurugan, P. Sriramya
• Keywords: GT Heuristic, Job Shop Scheduling, Multi-Objective

References

[1] Bruker, P., Scheduling Algorithms 2nd Edn, Springer-Verlag, Berlin (1995).

[2] Garey, M., et al., The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, (1976) pp.117-129.

[3] 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.

DOI: 10.1287/opre.24.4.774

[4] French, S., Sequencing and scheduling: An introduction to the mathematics of the job shop, New York, Wiley (1982).

[5] Mattfeld, D.C., Evolutionary Search and the Job Shop, Physica-Verlag, (1996).

[6] 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.

DOI: 10.1109/icec.1996.542658

[7] Bagchi, T.P., Multiobjective Scheduling By Genetic Algorithms, Kluwer Academic Publishers, (1999).

[8] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, (2001).

[9] Garen, J., Multi objective Job-Shop Scheduling with Genetic Algorithms Using a New Representation and Standard Uniform Crossover, MH Workshop, (2003).