Solving Multi Objective Job Shop Scheduling Problems Using Artificial Immune System Shifting Bottleneck Approach

Abstract:

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. Scheduling problems vary widely according to specific production tasks but most are NP-hard problems. Optimization of three practical performance measures mean job flow time, mean job tardiness and makespan are considered in this work. The Artificial Immune System Shifting Bottleneck Approach is used for finding optimal makespan, mean flow time, mean tardiness values of two benchmark problems. In this Artificial Immune System Shifting Bottleneck Approach (AISSB), initial sequences are generated with Artificial Immune System Algorithm (AIS) and Shifting Bottleneck Algorithm (SB) is used for finding final solutions. The results show that the AISSB Approach is effective algorithm that gives better results than literature results. The proposed AISSB Approach is an efficient problem-solving technique for multi objective job shop scheduling problem.

• Periodical: Applied Mechanics and Materials (Volumes 766-767)
• Pages: 1209-1213
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.766-767.1209
• Online since: June 2015
• Authors: S. Gopinath*, C. Arumugam, Tom Page, M. Chandrasekaran
• Keywords: Artificial Immune System Shifting Bottleneck Approach, Job Shop Scheduling, Multi Objectives

References

[1] JR Barker, GB Mcmahon, Scheduling the general job shop, Manufacturing Science, 31(7) (1985), 594–598.

DOI: 10.1287/mnsc.31.5.594

[2] P Brucker, B Jurisch, B Sievers, A branch and bound algorithm for the job shop scheduling problem, Discrete Applicable Mathematics, 49 (1994), 107–127.

DOI: 10.1016/0166-218x(94)90204-6

[3] C Chu, JM Proth, C Wang. Improving job shop schedules through critical pairwise exchanges, International Journal of Production Research, 36(5) (1998), 683–694.

DOI: 10.1080/002075498193633

[4] J Adams, E Balas, D Zawack, The shifting bottleneck procedure for job shop scheduling, Manufacturing Science, 34(5), (1988), 391–401.

DOI: 10.1287/mnsc.34.3.391

[5] J S Song, T E Lee, A tabu search procedure for periodic job shop scheduling, Computers and Industrial Engineering, 30(5), (1996), 433–447.

DOI: 10.1016/0360-8352(96)00012-5

[6] K Steinhöfel, A Albrecht, and CK Wong, Two simulated annealing-based heuristics for the job shop scheduling problem, European Journal of Operational Research, 118(5), (1999), 524–548.

DOI: 10.1016/s0377-2217(98)00326-9

[7] F Croce, R Tadei, and G Volta, A genetic algorithm for the job shop problem, Computers and Operational Research, 22 (1995), 15–24.

DOI: 10.1016/0305-0548(93)e0015-l

[8] M Chandrasekaran, P Asokan, S Kumanan, T Balamurugan, Solving job shop scheduling problem using Artificial Immune System, International Journal of Advanced Manufacturing Technology, 31(5), (2006), 580-593.

DOI: 10.1007/s00170-005-0226-3

[9] T.P. Bagchi Multi objective scheduling by Genetic Algorithms, Kluwer Academic Publishers, (1999).

[10] I Ono, M Yamamura, and S Kobayashi, A Genetic algorithm for job-shop scheduling problems using job-based order crossover, In Proceedings of ICEC '96, (1996), 547-552.

DOI: 10.1109/icec.1996.542658

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

[12] T Murata, I Hisao, H Tanaka, Multi-objective genetic algorithm and its applications to flow shop scheduling, Computers and Industrial Engineering, 30(6), (1996), 957–968.

DOI: 10.1016/0360-8352(96)00045-9

[13] J Garen, Multi objective Job-Shop Scheduling with Genetic Algorithms Using a New Representation and Standard Uniform Crossover, MOMH Workshop, Paris, (2002).