Um Algoritmo Genético Adaptativo para o problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção

• Fábio Fernandes Ribeiro CEFET-MG
• Marcone Jamilson Freitas Souza UFOP
• Sérgio Ricardo de Souza CEFET-MG

Resumo

Este trabalho trata do problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção, considerando janelas de entrega e tempo de preparação de máquina dependente da sequência de produção. Em vista da complexidade combinatória do problema, propõe-se resolvê-lo por meio de um algoritmo genético auto-adaptativo. Para cada indivíduo (sequência de tarefas) gerado utiliza-se um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa na sequência dada. Cinco operadores de cruzamento são utilizados para uma melhor exploração do espaço de soluções, sendo que a probabilidade de escolha de cada um deles depende do sucesso em buscas pregressas. Testes computacionais mostram a efetividade do algoritmo proposto.

Referências

Barcellos, J. C. H. d. (2000). “Algoritmos genéticos adaptativos: Um estudo comparativo”. Dissertação de mestrado, Escola Politécnica da USP, São Paulo.

Du, J. and Leung, J. Y. T. (1990). “Minimizing total tardiness on one machine is np-hard”. Mathematics of Operations Research, 15:483–495.

Feo, T. A. and Resende, M. G. C. (1995). “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6:109–133.

Glover, F. (1996). “Tabu search and adaptive memory programming - advances, applications and challenges”. In Barr, R. S., Helgason, R. V., and Kennington, J. L., editors, Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pages 1–75. Kluwer Academic Publishers.

Gomes Jr., A. C., Carvalho, C. R. V., Munhoz, P. L. A., and Souza, M. J. F. (2007). “A hybrid heuristic method for solving the single machine scheduling problem with earliness and tardiness penalties (in portuguese)”. In Proceedings of the XXXIX Brazilian Symposium of Operational Research (XXXIX SBPO), pages 1649–1660, Fortaleza, Brazil.

Hino, C. M., Ronconi, D. P., and Mendes, A. B. (2005). “Minimizing earliness and tardiness penalties in a single-machine problem with a common due date”. European Journal of Operational Research, 160:190–201.

Lee, C. Y. and Choi, J. Y. (1995). “A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights”. Computers and Operations Research, 22:857–869.

Matias, P. T. (2008). “Avaliação comparativa de algoritmos evolutivos com operadores adaptativos”. Dissertação de mestrado, Programa de Engenharia Civil, UFRJ, Rio de Janeiro.

Prais, M. and Ribeiro, C. C. (2000). “An application to a matrix decomposition problem in tdma traffic assignment”. INFORMS - Journal on Computing, 12:164–176.

Rossetti, I. C. M. (2003). “Estratégias sequenciais e paralelas de GRASP com reconexão por caminhos para o problema de síntese de redes a 2 caminhos”. Tese de doutorado, Programa de Pós-Graduação em Informática, PUC-RJ, Rio de Janeiro, Brasil.

Wan, G. and Yen, B. P. C. (2002). “Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties”. European Journal of Operational Research, 142:271–281.