» Download Article

Authors
Passos, Carlos Alberto dos Santos; Iha, Vitor Massaru; Dominiquini, Rafael Baboni

Digital Object Identifier (DOI)
10.3182/20100908-3-PT-3007.00038

Page Numbers:
198-203

Index Terms
Production Control, Control Systems; Artificial Intelligence and Multi-Agent Systems; Industrial Applications of Intelligent Systems

Abstract
This paper presents a multi-agents approach to solve job shop scheduling problem using meta-heuristics. The job shop scheduling problem (JSP) is a traditional problem largely exploited in the operational research area through the academic research but belonging also to the domain of practical situations, especially in industrial companies. Several approaches have been used to investigate this problem that is very complex when addressing real industrial cases. The JSP is a NP-hard problem and no exact solution can be obtained in polynomial time. Meta-heuristics approaches when solving scheduling problems have proven to be very effective and useful in practical situations. Among them, Tabu Search (TS) and Genetic Algorithms (GA) have been used to solve optimization problems with success. The main reason is that these algorithms have good performance in terms of solution quality and execution time, when compared with optimization or simple heuristics techniques respectively. In this sense, the multi-agent approach proposed in this paper combining these algorithms brings new perspective to solve this kind of problem. In this paper a multi-agent approach based on A-Team that combines TS and GA and other specific agents is presented to solve the JSP. Results for benchmark problems from the literature are presented aiming to demonstrate the applicability of the proposal.

References

REFERENCES
Baker, K.R. (1974). Introduction to Sequencing and Scheduling. John Wiley and Sons, Inc., New York.
Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society 41(11), pp1069-1072. 
French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop. John Willey & Sons Inc. New York, USA.
Glover, F.W., Kochenberger, G.A. (2002). Handbook of Metaheuristics, Kluwer Academic Publishers, Boston, MA, USA
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
Murthy, S., Rachlin, J., Akkiraju, R., Wu, F. (1997). Agent-Based Cooperative Scheduling; In Constraints & Agents, Technical Report WS 1997-97-05, Menlo Park, AAAI Press.
Nawaz, M., Enscore, E. E., Ham, I., “A heuristic algorithm for the m-machine, n-job flow shop sequencing problem”. OMEGA, Int. J. Of Management Science, 11(1): 91-95.
ORLIB - http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/ jobshop1.txt
Passos, C.A.S., Fonseca, S.L.A. (2003). Scheduling of jobs in chemical process industries using metaheuristics approaches. International Conference on Industrial Logistics - ICIL’2003 16, Vaasa, Finland.
Passos, C.A.S., Fonseca, S.L.A (2004). Scheduling of Industrial Jobs Using An A-Team Approach. The Symposium on Professional Practice in AI, 18th IFIP World Computer Congress, Toulouse, France, ISBN 2-907801-05-8, p 1 –10.
Pezzella, F., Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem – European Journal of Operational Research. 120, p 297-310.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, p. 278-285.
Talukdar, S.N., Souza, P.S. (1992). Scale efficient organizations, IEEE Int. Conference on Systems, Man and Cybernetics.
Talukdar, S.N.; Souza, P.S. (1990). Asynchronous Teams. Second SIAM Conference on Linear Algebra: Signals, Systems and Control.
Wooldridge, M. (2002). An Introduction to MultiAgent Systems. John Wiley & Sons Ltd, paperback, 366 pages, ISBN 0-471-49691-X.
Yamada, T., Nakano, R. (1997). Genetic Algorithms for Job-shop Scheduling Problems. Proceedings of Modern Heuristic for Decision Support. Pp. 67-81, UNICOM Seminar, 18-19 March 1997, London.