An AIS-based Hybrid Algorithm with PSO for Job Shop Scheduling Problem

Job Shop Scheduling Problem (JSSP) is a traditional NP-hard combinational optimization problem. In this paper, we propose a new hybrid method based on Artificial Immune Systems (AIS) and Particle Swarm Optimization (PSO) to solve JSSP with an objective of minimizing the makespan while satisfying the predefined constraints. Two AIS theories, namely, clonal selection theory and immune network theory are adopted. The former establishes the fundamental processes including selection, cloning, hypermutation and receptor editing, and the latter increases the diversity for the potential solution set. For the random hypermutation process, PSO is applied to optimize and accelerate the search process. This algorithm is tested on 20 benchmark problems with four different sizes. The results shows that its performance is encouraging, especially for small size problems.