Solving job shop scheduling problems using artificial immune system

摘要

The n-job, m-machine job shop scheduling (JSS) problem is one of the general production scheduling problems. Many existing heuristics give solutions for small size problems with near optimal solutions. This paper deals with the criterion of makespan minimization for the job shop scheduling of different size problems. The proposed computational method of artificial immune system algorithm (AIS) is used for finding optimal makespan values of different size problems. The artificial immune system algorithm is tested with 130 benchmark problems [10 (ORB1-ORB5 & ARZ5-ARZ9), 40 (LA01-LA40) and 80 (TA01-TA80)]. The results show that the AIS algorithm is an efficient and effective algorithm which gives better results than the Tabu search shifting bottleneck procedure (TSSB) as well as the best solution of shifting bottleneck procedure ( SB-GLS1 ) of Balas and Vazacopoulos.