A multi Agent System Based on Modified Shifting Bottleneck and Search Techniques for Job Shop Scheduling Problems

Document Type : Research Article

Authors

Abstract

This paper presents a multi agent system for the job shop scheduling problems. The proposed system consists of initial scheduling agent, search agents, and schedule management agent. In initial scheduling agent, a modified Shifting Bottleneck is proposed. That is, an effective heuristic approach and can generate a good solution in a low computational effort. In search agents, a hybrid search approach is presented. The schedule management agent can manage the system. Finally, the proposed agent based system is tested and validated by some benchmark problems. The results show the superiority of the proposed system in terms of makespan minimization and CPU times.

Keywords

References

[1]     J. Adams, E. Balas, D. Zawack, "The shifting bottleneck procedure for job shop scheduling," Management Science, 34, 391–401, 1988.
[2]     K. Anke, R Staudte and W. Dilger, Producing and improving timetables by means of constraints and agents, Technical Report WS-97-05, AAAI Press, Menlo Park, CA,pp. 142-147, 1997.
[3]     D. Applegate, W. Cook, "A computational study of job shop scheduling problem," ORSA Journal of Computing, 3149–156, 1991.
[4]     M. E. Aydin, T.C. Fogarty, Teams of autonomous agents for job-shop scheduling problems: An Experimental Study, Journal of Intelligent Manufacturing, 15(4), (2004) 455–462.
[5]     E. Balas, J.K. Lenstra, Vazacopoulos, "The One machine Problem with Delayed Precedence Constraints and its use in Job Shop Scheduling," Management Science, 41, 1, 94-109, 1995.
[6]     E. Balas, A.Vazacopoulos, Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2):262–75, 1998.
[7]     J Blazewicz, W Domschke, E. Pesch, The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, 93, 1–33, 1996.
[8]     P. Burke and P. Prosser, The Distributed Asynchronous Scheduler, in: Intelligent Scheduling, M.B. Morgan, ed., Morgan Kaufman Publishers, Inc., San Francisco,  pp. 309–339, 1994.
[9]     J. Carlier, "The one-machine sequencing problem," European Journal of Operational Research, 11, 42-47, 1982.
[10]  S. Dauzere-Peres, J.B. Lasserre," A modified shifting bottleneck procedure for job-shop scheduling," International Journal of Production Research, 31, 923-932, 1993.
[11]  M. Dell’Amico, Trubian M. Applying tabu-search to job-shop scheduling problem.Annals of Operations Research, 41,231–52, 1993.
[12]  E. Demirkol, S.V. Mehta, R. Uzsoy," A computational study of shifting bottleneck procedures for shop scheduling, " J. Heuristics, 3, 111–137, 1997.
[13]  U. Dorndorf, E. Pesch, Evolution based learning in a job shop scheduling environment. Comput. Oper. Res., 22, 25–44, 1995.
[14]  J. Ferber, (1999) Multi-agent systems: An introduction to Distributed Artificial Intelligence. Addison Wesley, London.
[15]  H. Fisher and D.L. Thompson, "Probabilistic learning combinations of local job shop scheduling rules," In J. F. Muth, G. L. Thompson (eds.), Industrial Scheduling, Prentice-Hall, Englewood Cliffs, 1963.
[16]  M.R. Garey, D.S. Johnson, "Computers and Intractability: A Guide to the Theory of NP Completeness," San Francisco Freeman, 1979.
[17]  F. Glover, M. Laguna, Tabu search. Dordrecht: Kluwer Academic Publishers; 1997.
[18]  AS. Jain, S. Meeran, Deterministic job shop scheduling: past, present and future. European Journal of Operational Research, 113, 390–434, 1999.
[19]  E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, "Recent developments in deterministic sequencing and scheduling: a survey" in M. A. H. Dempster, J.K.  Lenstra and A.H.G. Rinnooy Kan , Deterministic and Stochastic Scheduling, Reidel, Dordrecht, 1982.
[20]  HD Matsuo, CJ Suh, RS Sullivan, A controlled search simulated annealing method for general job shop scheduling problem. Working Paper, 03-04-88, Department of Management, The University of Texas at Austin, Austin, TX, 1988.
[21]  G.B. McMahon and M. Florian, "On scheduling with ready times and due dates to minimize maximum lateness,” Operations Research, 23, 415-482, 1975.
[22]  S. Mukherjee and A.K. Chatterjee, "On the representation of the one machine sequencing problem, " Eur. J. Oper. Res, doi:10.1016/j.ejor.2006.07.024.
[23]  S. Murthy, “Synergy in Cooperating Agents: Designing Manipulators from Task Specifications,” Ph.D. dissertation, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 1992.
[24]  E. Nowicki, C. Smutnicki, A fast taboo search algorithm for the job shop scheduling problem.Management Science, 42, 6, 797–813, 1996.
[25]  L. Schrage, "Obtaining optimal solutions to resource constrained network scheduling problem," Unpublished manuscript 1971.
[26]  M Sevkli, M. E. Aydin, Variable Neighbourhood Search for Job Shop Scheduling Problems, Journal of software, V.1, N. 2, August 2006.
[27]  W. Shen, Q. Hao, H. J. Yoon, D.H. Norrie, Applications of agent-based systems in intelligent manufacturing:An updated review, Advanced Engineering Informatics 20 (2006) 415–431.
[28]  S.Talukdar, Asynchronous teams. Proceedings of the 4th international symposium on expert systems applications to power systems, LaTrobe university,Melbourne, Australia.
[29]  A. Tharumarajah and R. Bemelman, Approaches and issues in scheduling a distributed shop floor environment, Computers in industry, 34, 95-109, 1997.
[30]  R. Uzsoy and C.S. Wang, "Performance of decomposition procedures for job shop scheduling problems with bottleneck machines," Int. J. Prod. Res., 38, 1271–1286, 2000.
[31]  PJM. Van Laarhoven, EHL Aarts, JK. Lenstra, Job shop scheduling by simulated annealing. Operations Research , 40, 1, 113–125, 1992.
[32]  H. Wenqi and Y. Aihua, "An improved shifting bottleneck procedure for the job shop scheduling problem," Computer & Operations Research, 31, pp. 2093-2110, 2004.
[33]  M. Wooldridge, An introduction to multi-agent systems. John Wiley & Sons, Ltd., Chichester, England. , 2002.
[34]  C.S. Wu, D.C. Li, T.I. Tsai, "Applying the fuzzy ranking method to the shifting bottleneck procedure to solve scheduling problems of uncertainty," Int. J. Adv. Manuf. Technol., 31, 98–106, 2006.
[35]  C.Y. Zhang, P. Li, Z. Guan, Y. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem Computers & Operations Research doi:10.1016/j.cor.2005.12.002.
[36]  Z. D. Zhou, H. H. Wang, Y. P. Chen, W. Ai, S. K. Ong, J. Y. H. Fuh and A. Y. C. Nee, A Multi-Agent-Based Agile Scheduling Model for a Virtual Manufacturing Environment, Int. J Adv Manuf. Technol., 21, 980–984, 2003.

Files

Share

How to cite

Statistics