Multi-agent Method Based On Bottleneck For Solving Job Shop Scheduling

With the rapid speed of the expanding of industrialization,the production lines of manufactory are becoming more and more complex and in today's competitive market,the requirements of quick respond to the orders are growing as well.So that achieving a good schedule becomes one of the most important key elements of manufactory.Job shop scheduling is a classical scheduling problem and be researched from the middle of last century.In job shop scheduling problem,when one or several activities'start time have been changed,it may cause the conflicts in the system.So finding a method with high efficiency to adjust the scheduling is the top priority.Because the multi-agent method can get a feasible solution rapidly,this method is selected to solve the problem.Multi-agent method contains a set of different agents,each agent solve the conflicts on purpose.Different agents coordinate with each other by using search knowledge.When there is no conflicts in ether of the agent,then the system get the solution.Each agent owns the strong ability of solving the problem is the reason this method could rapidly get a solution.According to the researches on scheduling theories,the bottleneck machine has the tightest constrains in the system,so it can assume that the most of the performance of a schedule is determined by bottleneck machine.So in order to get better solution,the paper combines the multi-agent method with bottleneck strategy.First select the bottleneck machine and then optimizes the bottleneck machine.There are three kinds of agent:job agent,machine agent and bottleneck machine agent.The optimal way is presented in two parts,one is initial the bottleneck machine and the other is solving the conflicts.The improved method has better performance.But from the main scheme of system,the solving process is a circular iteration that has potential risk of falling into deadlock.After test numerous of experiments,three kinds of deadlock are been found and the reasons are summarized.For simplicity the paper utilizes two methods to solve the deadlock that exist in this multi-agent system.One is prevent the deadlocks,the other is find the deadlocks and deal with them.This methodology not only can get a good schedule in short time,but also solve the shortcoming of the multi-agent method:deadlock.The experiments result shows that it is successfully modify the algorithm to avoid all the deadlocks in the small size problem.Because the bigger size problem's machine assignment is huge,it is impossible to test all of the configurations.So the paper just test for hundreds of times and does not detect any remained deadlocks.For the same problem,the improved method can get a better solution than the previous one.Although the improved method's running time is longer than the dispatching rule,the improved method could get better solution.When the improved method compare with taboo search,for solving some of the problem,improved method can get a similar schedule with taboo search.