A local search genetic algorithm for the job shop scheduling problem with intelligent agents

The job shop scheduling problem is one of the most important and complicated problems in machine scheduling and is considered to be a member of a large class of intractable numerical problems known as NP-hard. Genetic algorithms have been implemented successfully in many scheduling problems, in particular job shop scheduling. Hybridization is an effective way of improving the performance and effectiveness of genetic algorithms. Local search techniques are the most common form of hybridization that can be used to enhance the performance of these algorithms. Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. This paper presents an agent-based local search genetic algorithm for solving the job shop scheduling problem. A multi agent system containing various agents each with special behaviors is developed to implement the local search genetic algorithm. Benchmark instances are used to investigate the performance of the proposed approach. The results show that the proposed agent-based local search genetic algorithm improves the efficiency.