Hybrid Method for Solving Flexible Open Shop Scheduling Problem with Simulated Annealing Algorithm and Multi-Agent Approach

Abstract:

In this study we propose metaheuristic optimization algorithm, in which simulated annealing, multi agent approach with fuzzy logic are used. On the first level of solution search the multi agent approach is used, and on the second level – the simulated annealing. Two types of routing were considered: a serial and a parallel one. The multi-agent approach emphasizes flexibility rather than the optimality of solutions. On the other hand, search approaches such as simulated annealing, which focus more on the optimality of solutions.

• Periodical: Advanced Materials Research (Volumes 383-390)
• Pages: 4612-4619
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.383-390.4612
• Online since: November 2011
• Authors: Tadeusz Witkowski, Paweł Antczak, Arkadiusz Antczak
• Keywords: Component, Fuzzy Logic, Job Shop Scheduling, Meta-Heuristic, Multi Agent Approach, Open Shop Scheduling, Simulated Annealing (SA)

References

[1] M. Paolucci, and R. Sacile, Agent-Based Manufacturing and Control Systems, CRC Press, Boca Raton, London, New York, Washington, D.C., (2005).

[2] M.E. Aydin, and T.C. Fogarty, Simulated annealing with evolutionary processes in job shop scheduling, in Evolutionary Methods for Design, Optimization and Control, Proc. of Eurogen 2001, Athenes 2001, CIMNE, Barcelona (2002).

[3] H. Brasel, T. Tautenhahn, and F. Werner, Constructive Heuristic Algorithms for the Open-Shop Problem, Computing, vol. 51, 1993, pp.95-110.

DOI: 10.1007/bf02243845

[4] H. Brasel, A. Herms, M. Morig, T. Tautenhahn, J. Tusch, and F. Werner, Heuristic Algorithms for Open Shop scheduling to Minimize Mean Flow Time, Part I: Constructive Algorithms, www. Math. Uni-magdeburg. de/~werner/preprints/pp.06-48. pdf.

DOI: 10.1016/j.ejor.2007.02.057

[5] U. Dorndorf, E. Pesch, and T. Phan-Huy, Solving the Open Shop Scheduling Problem, Journal of Scheduling, vol. 4, 2001, pp.157-174.

DOI: 10.1002/jos.73

[6] H. -L. Fang, P. Ross, and D. Corne, A Promising Hybrid GA/Heuristic Approach for Open Shop Scheduling Problems, Proc. of the 11th European Conference on Artificial Intelligence, John Wiley and Sons, 1994, pp.590-594.

[7] P. Fattahi, A hybrid Multi Objective Algorithm for Flexible Job Shop Scheduling, Proc. of World Academy of Science, Engineering and Technology, vol. 38, 2009, pp.555-560.

[8] C. Gueret, and C. Prins, Classical and New Heuristics for the Open-Shop Problems: A Computational Evaluation, European Journal Operation Research, 107, 1998, pp.306-314.

DOI: 10.1016/s0377-2217(97)00332-9

[9] N. Imanipour, and S.H. Zegordi, A heuristic Approach Based on Tabu Search for Early/Tardy Flexible Job Shop Problems, Scientia Iranica, vol. 13, N 1, 2006, pp.1-13.

[10] K. Jansen, M. Mastrolilli, and R. Solis-Oba, Approximation algorithms for flexible job shop problems, Proc. of Latin American Theoretical Informatics, LNCS 1776, 2000, pp.68-77.

DOI: 10.1007/10719839_7

[11] Y. K. Kim, K. Park, and J. Ko, Symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Computers & Operations Research, 30, 2003, pp.1151-1171.

DOI: 10.1016/s0305-0548(02)00063-1

[12] G.J. Kyparisis, and C. Koulamas, Open Shop Scheduling with Makespan and Total Completion Time Criteria, Comput. Operations Research, vol. 27, 2000, pp.15-27.

DOI: 10.1016/s0305-0548(99)00005-2

[13] C.F. Liaw, Iterative Improvement Approach for the Nonpreemptive Open Shop Scheduling Problem, European Journal Operations Research, vol. 111, 1998, pp.509-517.

DOI: 10.1016/s0377-2217(97)00366-4

[14] C.F. Liaw, A hybrid genetic Algorithm for the open shop scheduling problem, European Journal Operation Research, vol. 124, 2000, pp.28-42.

DOI: 10.1016/s0377-2217(99)00168-x

[15] T., Satake, K. Morikawa, K. Takahashi, and N. Nakamura, Simulated annealing approach tor minimising the makespan of the general job-shop, International Journal of Production Economics, 60-61, 1999, pp.515-522.

DOI: 10.1016/s0925-5273(98)00171-6

[16] D.Y. Sha, and Ch. - Yu Hsu, A new particle swarm optimization for the open shop scheduling problem, Computers and Operations Research, vol. 35, issue 10, October 2008, pp.3243-3261.

DOI: 10.1016/j.cor.2007.02.019

[17] L. Sakalauskas, G. Felinskas, Optimization of Resource-Constrained Project Schedules by Simulated Annealing and Variable Neighborhood Search, Technological and Economic Development of Economy, vol. 12, N 4, 2006, pp.307-313.

DOI: 10.3846/13928619.2006.9637759

[18] K. Steinhofel, A. Albrecht, C.K. Wong, Fast parallel heuristics for the job shop, scheduling problem, Computer & Operations Research, 29, 2002, pp.151-169.

DOI: 10.1016/s0305-0548(00)00063-0

[19] M. Yazdani, M. Gholami, M, Zandieh, and M. Mousakhani, A Simulated Annealing Algorithm for Flexible Job Shop Scheduling Problem, Journal of Applied Sciences, 2009, pp.1-9.

DOI: 10.3923/jas.2009.662.670

[20] T. Gabel, and M. Riedmiller, On a Succesful Application of Multi-Agent Reinforcement Learning to Operations Research Benchmarks, Proc. of the 2007 IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning, pp.68-75.

DOI: 10.1109/adprl.2007.368171

[21] A. Kazemi, and M.H. F. Zarandi, An Agent Based Framework for Bulding Decision Support System in Supply Chain Management, Journal of Applied Sciences 8 (7), 2008, pp.1125-1137.

DOI: 10.3923/jas.2008.1125.1137

[22] J. Madejski, Agent architecture for intelligent manufacturing systems, Journal of Achievements in Materials and Manufacturing Engineering, vol. 29, issue 2, August 2008, pp.167-170.

[23] J. L. Pollock, Against Optimality: Logical Foundations For Decision - Theoretical Planning In Autonomous Agents, Computional Intelligence, vol. 22, N 1, 2006, pp.1-25.

DOI: 10.1111/j.1467-8640.2006.00271.x

[24] V. Thiagarasu, and T. Devi, Multi-Agent Coordination in Project Scheduling: Priority Rules Based Resource Allocation, International Journal of Recent Trends in Engineering, vol. 1, No 2, May 2009, pp.42-46.

[25] Z. Wang, X. Li, and X. Qi, The Design and Devolopment of a Multiagent Agile Scheduling System, International Journal of Computational Intelligence Research, vol. 4, N 1, 2008, pp.45-52.

[26] I. Badr, An Agent-Based Scheduling Frameqork for Flexible Manufacturing Systems, Proc. of World Academy of Science, Engineering and Technology, vol. 30, July 2008, pp.363-369.

[27] W. Shen, and D.H. Norie, Agent-Based Systems for Intelligent Manufacturing: A Stste-of-the-Art Survey, Knowlegde and information Systems, an International Journal, vol. 1, N 2, 1999, pp.129-156.

[28] W. Shen, Distributed manufacturing scheduling using intelligent agents, IEEE Intelligent Systems, January/ February, 88, (2002).

DOI: 10.1109/5254.988492

[29] T. Witkowski, P. Antczak, and A. Antczak, Application of GRASP procedure for production scheduling and its comparision with other methods, Journal of Automation and Information Sciences, Beggel House Inc., New York 2005, vol. 37, 6(40), pp.35-40.

[30] T. Witkowski, P. Antczak, and A. Antczak, The application of simulated annealing procedure for the flexible job shop scheduling problem, Proc. 11th International Conferene Information Processing and Management of Uncertainty in Knowledge-Based Systems (Industrial Track), Paris 2006, pp.21-26.

DOI: 10.1109/aici.2010.212