Design and Implementation of a Multi-Agent System for the Job Shop Scheduling Problem

Job shop scheduling is one of the strongly NP-complete combinatorial optimization problems. Developing effective search methods is always an important and valuable work. Meta-heuristic methods such as genetic algorithms are widely applied to find optimal or near-optimal solutions for the job shop scheduling problem. Parallelizing genetic algorithms is one of the best approaches that can be used to enhance the performance of these algorithms. In this paper, we propose an agent-based parallel genetic algorithm for the job shop scheduling problem. In our approach, initial population is created in an agent-based parallel way then an agent-based method is used to parallelize the genetic algorithm. Experimental results showed that the proposed approach enhances the performance.