A Hybrid AIS-based Algorithm for Solving Job Shop Scheduling Problem

Artificial Immune Systems (AIS) is a relatively new metaheuristics inspired by the human immune system. In this paper, we investigate two theories of AIS, namely, clonal selection theory and immune network theory, and integrate them with Particle Swarm Optimization (PSO) to solve the classical NP-hard optimization problem - the Job Shop Scheduling Problem (JSSP) with the objective of makespan minimization. In this hybrid algorithm, clonal selection theory is used to set up the framework which contains the processes of selection, cloning, hypermutation and receptor editing, while the immune network theory is applied to increase the diversity of the potential solution repertoire. The PSO is modified and hybridized in the mutation process to optimize the search procedure. To demonstrate the effectiveness of PSO and efficiency of the hybrid algorithm, 20 benchmark problems of different scales are used. The results are promising and encouraging, especially for small size instances.