Hybrid genetic algorithms: solutions in realistic dynamic and setup dependent job-shop scheduling problems
DOI:
https://doi.org/10.4995/ijpme.2016.5780Keywords:
genetic algorithms, dispatching rules, realistic job-shop schedulingAbstract
This paper discusses the application of heuristic-based evolutionary technique in search for solutions concerning the dynamic job-shop scheduling problems with dependent setup times and alternate routes. With a combinatorial nature, these problems belong to an NP-hard class, with an aggravated condition when in realistic, dynamic and therefore, more complex cases than the traditional static ones. The proposed genetic algorithm executes two important functions: choose the routes using dispatching rules when forming each individual from a defined set of available machines and, also make the scheduling for each of these individuals created. The chromosome codifies a route, or the selected machines, and also an order to process the operations. In essence , each individual needs to be decoded by the scheduler to evaluate its time of completion, so the fitness function of the genetic algorithm, applying the modified Giffler and Thomson’s algorithm, obtains a scheduling of the selected routes in a given planning horizon. The scheduler considers the preparation time between operations on the machines and can manage operations exchange respecting the route and the order given by the chromosome. The best results in the evolutionary process are individuals with routes and processing orders optimized for this type of problema.
Downloads
References
Araujo, L. O. (2006). Método de Programação de Sistemas de Manufatura do Tipo Job Shop Dinâmico Não Determinístico. Tese (doutorado), Universidade de São Paulo, São Paulo.
Barboza, A. O. (2005). Simulação e técnicas da computação evolucionária aplicadas à problemas de programação linear inteira mista, Tese (doutorado), Universidade Tecnológica Federal do Paraná. Paraná.
Branco, R. M. (2010). Agendamento de tarefas em sistemas de manufatura job-shop realista com demanda por encomenda: solução por algoritmo genético, Tese (doutorado), Universidade Federal de Santa Catarina.
Chan, F. T. S. (2003). Effects of dispatching and routeing decisions on the performance of flexible manufacturing system. International Journal of Advanced Manufacturing Technology, 21(5), 328-338. doi:10.1007/s001700300038
Chiang, T-C., Fu, L-C. (2006). Using Dispatching Rules for Job Shop Scheduling with Due Date-based Objectives, Proceedings of the 2006 IEEE International Conference on Robotics and Automation, Orlando, Florida. doi:10.1109/ROBOT.2006.1641909
El-Bouri, A., Shah, P. (2006). A neural network for dispatching rule selection in a job shop. The International Journal of Advanced Manufacturing Technology, 31(3), 342-349. doi:10.1007/s00170-005-0190-y
Giffler, B., Thompson, G. (1960). Algorithms for solving production scheduling problems. Operations Research, 8(4), 487-503. doi:10.1287/opre.8.4.487
Goldbarg, M. C., Luna, H. P. L. (2000). Otimização Combinatória e Programação Linear. 2 Ed. Editora Campus.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. US: New York
Gonçalves, J. F., de Magalhães Mendes, J. J., Resende, M. G. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European journal of operational research, 167(1), 77-95. doi:10.1016/j.ejor.2004.03.012
Herrmann, J. W., Lee, C.-Y., Hinchman, J. (1995). Global job shop scheduling with a genetic algorithm. Production and Operations Management, 4(1), 30-45. doi:10.1111/j.1937-5956.1995.tb00039.x
Jain, A. S., Meeran, S. (1998). A state-of-the-art review of job-shop scheduling techniques, Technical Report, Department of Applied Physics, Electronics and Mechanical Engineering, University of Dundee, Scotland.
Johnson, S. M., (1954). Optimal two and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68. doi:10.1002/nav.3800010110
Kumar, R., Tiwari, M. K., Shankar, R. (2003). Scheduling of flexible manufacturing systems: an ant colony optimization approach. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 217(10), 1443-1453. doi:10.1243/095440503322617216
Linden, R. (2008). Algoritmos genéticos. Brasport, 2 edição. 2008.
Mauri, G. R., Lorena, L. A. N. (2006). Simulated Annealing Aplicado a um Modelo Geral do Problema de Roteirização e Programação de Veículos. XXXVIII SBPO - Simpósio Brasileiro de Pesquisa Operacional. Goiânia, GO.
Matsusaki, C. T. M. (2004). Modelagem de Sistemas de Controle Distribuídos e Colaborativos De Sistemas Produtivos. Tese (doutorado), Universidade de São Paulo, São Paulo. doi:10.11606/t.3.2004.tde-20122004-112454
Mayerle, S. F. (1994). Um algoritmo genético para a solução do caixeiro viajante. Tecnical Report, Departamento de Engenharia de Produção e Sistemas, UFSC.
Porter, K., Little, D., Peck, M., Rollins, R. (1999). Manufacturing classifications: relationship with production control systems. Integrated Manufacturing Systems, 10(3-4): 189-198. doi:10.1108/09576069910280431
Singh, A., Mehta, N. K., Jain, P. K. (2007). Multicriteria dynamic scheduling by swapping of dispatching rules. InternationalJournal of Advanced Manufacturing Technology, 34(9), 988-1007. doi:10.1007/s00170-006-0674-4
Vázquez, M., Whitley, D. (2000). A comparison of Genetic Algorithms in solving the Dynamic Job Shop Scheduling Problem. GECCO. Available in https://docs.google.com/file/d/0B0xb4crOvCgTMXpKRnp6NFo3bTQ/edit
Wall, M. B. (1996). A Genetic Algorithm for Resource-Constrained Scheduling, Tesis, Departament of Mechanical Engineering, Massachusetts Institute of Technology.
Downloads
Published
How to Cite
Issue
Section
License
This work as of Vol. 11 Iss. 2 (2023) is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike- 4.0 International License
