Collaboration of Multi-Agent and Hyper-Heuristics Systems for Production Scheduling Problem

Authors: C. E. Nugraheni, L. Abednego

Abstract:

This paper introduces a framework based on the collaboration of multi agent and hyper-heuristics to find a solution of the real single machine production problem. There are many techniques used to solve this problem. Each of it has its own advantages and disadvantages. By the collaboration of multi agent system and hyper-heuristics, we can get more optimal solution. The hyper-heuristics approach operates on a search space of heuristics rather than directly on a search space of solutions. The proposed framework consists of some agents, i.e. problem agent, trainer agent, algorithm agent (GPHH, GAHH, and SAHH), optimizer agent, and solver agent. Some low level heuristics used in this paper are MRT, SPT, LPT, EDD, LDD, and MON

Keywords: Hyper-heuristics, multi-agent systems, scheduling problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1087874

References:

[1] Burke E. K., Hyde M., Kendall G., Ochoa G., Ozcan E., and Qu R. "Hyperheuristics: A Survey of the State of the Art". 2010.
[2] Burke E. K., Hart E., Kendall G., Newall J., Ross P., and S. Schulenburg. "Hyperheuristics: An emerging direction in modern search technology." In F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics. Kluwer, pp. 457-474. 2003.
[3] Silva J.D.L., Burke E.K., Petrovic S. "An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling." 2005.
[4] Burke E.K., Hyde M., Kendall G., Ochoa G., Ozcan E., and Woodward J. "Exploring hyper-heuristic methodologies with genetic programming." In Mumford C, Jain L (eds) Computational Intelligence: Collaboration, Fusion and Emergence, Intelligent Systems Reference Library, Springer, pp 177-201. 2009.
[5] Burke E. K., Hyde M., Kendall G., Ochoa G., Ozcan E., and Qu R. "Hyperheuristics: A Survey of the State of the Art." 2010.
[6] Bolat, A., Al-Harkan, I., and Al-Harbi, B., (2005), "Flow-shop Scheduling for Three Serial Stations with the Last Two Duplicate ", Computers and Operations Research. 2005.
[7] Blackstone J. H., Phillips D. T., and Hogg G. L. “A state-of-the-art survey of dispatching rules for manufacturing job shop operations.” In International Journal of Production Research, 20(1), 27-45. 1982.
[8] Oliver, H., Chandrasekharan, R. "E?cient dispatching rules for scheduling in a job shop." International Journal of Production Economics, 48(1), 87-105. 1997.
[9] Man K.F., Tang K.S. and Kwong S. "Genetic Algorithms: Concepts and Design." Springer. 1999.
[10] Vazquez-Rodriguez J.A., Petrovic S., Salhi A. "A combined metaheuristic with hyper-heuristics approach to the scheduling of the hybrid ?ow shop with sequence dependent setup times and uniform machines." In Proceedings of the 3rd Multidisciplinary International Scheduling Conference: Theory and Applications. 2007.
[11] Abednego L. "Genetic Programming Hyper-Heuristics For Solving Dynamic Production Scheduling Problem". 2011.Proc. ICEEI 2011.
[12] Ruibin Bai, Edmund K. Burke, Graham Kendall, and Barry McCollum. "A Simulated Annealing Hyper-heuristic for University Course Timetabling." PATAP 2006. pp. 345-350. 2006.