Hybrid genetic algorithms: solutions in realistic dynamic and setup dependent job-shop scheduling problems

Rogério M. Branco, Antônio S. Coelho, Sérgio F. Mayerle

Abstract

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.


Keywords

genetic algorithms; dispatching rules; realistic job-shop scheduling

Full Text:

PDF

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.

Abstract Views

1319
Metrics Loading ...

Metrics powered by PLOS ALM




This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives- 4.0 International License 

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317   https://doi.org/10.4995/ijpme