Multi-Agent and Hybrid Genetic Algorithm Approach for Distributed Jobshop Scheduling

摘要

Jobshop scheduling is a typical NP hard problem. In the distributed manufacturing environment, it becomes a more intractable one with the characters of distributed object, multiple target and strong dynamic. A novel distribution jobshop scheduling method based on multi-agent mechanism and genetic algorithm is presented. A distributed scheduling system framework, which composed of several jobshop agents, task agents, and resource agents, is established firstly. With the distribution of agents, the complex distributed scheduling problem is transformed into several sub-problems, such as local optimization scheduling of individual agent and global optimization of the multi-agent system. Then, a hybrid genetic algorithm is elaborated to support agents to do their scheduling decisions. In order to further improve capacities of the algorithm, a new solution is proposed, which allowing agents to participate in the optimizing process of the genetic algorithm. Finally, a prototype system for multi-shop distributed scheduling is developed and the simulation results are given to illustrate the feasibility and efficiency of the approach.