An Investigation On Multi-Agent Based Job Shop Scheduling System

Job shop Scheduling is an optimization process that allocates limited manufacturing resources over time among parallel and sequential manufacturing activities. This allocation must obey a set of rules or constraints that reflect the temporal relationship between manufacturing activities and the capacity limitations of a set of shared resources. The allocation also affects a schedule's optimality with respect to criteria such as cost, lateness or throughput. The uncertainty of modern manufacturing environment and the dynamic need of customers make job shop scheduling increasingly complex. In order to deal with such challenges, job shop scheduling systems should be more adaptive, robust and flexible. In this study, we propose a multi-agent job shop scheduling system based on combinational auction methodology.First of all, basic background of job shop scheduling problem and related works are given. It can be predicted that the scheduling algorithms will be more integrated, dynamic, effective, intelligent and useful in the future.Secondly, multi-agent system theory is introduced in detail which is one of the most important topics in distributed artificial intelligence research.Thirdly, a new multi-agent based job shop scheduling system is designed which involves four agents: scheduling agent, task agent, resource agent and auction agent. These four agents cooperate with each other to complete the job shop scheduling.Fourthly, negotiation strategy of designed scheduling system is discussed. In fact negotiation strategy of multi agent system immediately impacts its performance. Traditionally, contract net is used in a lot researches, however, it is not very suitable in scheduling system. In this research, combinational auction base negotiation strategy is adopted and an auction based scheduling algorithm is given.Finally, a case study of designed job shop scheduling system is given. It shows that our research illustrates a possible way to make job shop scheduling much more effective, intelligence and useful.