An E²GPGP-GASA-Based Multi-Agent Job Shop Scheduling System

Abstract:

In this paper, a job shop scheduling model combining MAS (Multi-Agent System) with GASA (Simulated Annealing-Genetic Algorithm) is presented. The proposed model is based on the E²GPGP (extended extended generalized partial global planning) mechanism and utilizes the advantages of static intelligence algorithms with dynamic MAS. A scheduling process from ‘initialized macro-scheduling’ to ‘repeated micro-scheduling’ is designed for large-scale complex problems to enable to implement an effective and widely applicable prototype system for the job shop scheduling problem (JSSP). Under a set of theoretic strategies in the GPGP which is summarized in detail, E²GPGP is also proposed further. The GPGP-cooperation-mechanism is simulated by using simulation software DECAF for the JSSP. The results show that the proposed model based on the E²GPGP-GASA not only improves the effectiveness, but also reduces the resource cost.

• Periodical: Advanced Materials Research (Volume 505)
• Pages: 65-74
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.505.65
• Online since: April 2012
• Authors: Lin Lin Lu, Xin Ma, Ya Xuan Wang
• Keywords: Extended Extended Generalized Partial Global Planning, Job Shop Scheduling Problem, Multi-Agent System (MAS), Simulated Annealing-Genetic Algorithm

References

[1] B Jacek, et. al. The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 1996,93(1):1~33

DOI: 10.1016/0377-2217(95)00362-2

[2] K Decker, V R Lesser. Generalizing the partial global planning algorithm. Journal of Intelligent and Cooperative Information Systems, 1992, 1(2): 319~346.

DOI: 10.1142/s0218215792000222

[3] K Decker, J Li. Coordinating mutually exclusive resources using GPGP. Journal of Autonomous Agents and Multi-Agent Systems, 2000, 22(3):1~27.

[4] V R Lesser, K Decker, N Carver, et. al. Evolution of the GPGP/TAEMS domain - independent coordination framework. Journal of Autonomous Agents and Multi-Agent Systems, 2004, (9):87~143

DOI: 10.1023/b:agnt.0000019690.28073.04

[5] K Decker, V R Lesser. Designing a family of coordination algorithms. In: Proceedings of the First International Conference on Multi-Agent Systems. San Francisco, USA: AAAI Press, 1995.73~80.

[6] G M P O'Hare, N R Jennings. Foundations of Distributed Artificial Intelligence. New York: John Wiley & Sons, 1996.

[7] K Decker. Coordinating intelligent agents. In: Foundations and Applications of Multi-Agent Systems: UKMAS Workshop 1996-2000. Heidelberg, GER: Springer Berlin, 2002. 1~18

[8] T Sugawara, V R Lesser. Learning to improve coordinated actions in cooperative distributed problem-solving environments. Journal of Machine Learning, 1999, 33(2): 101~110