GRASP Reativo e Iterated Local Search aplicado ao problema de programação de tarefas em máquinas paralelas com tempos de preparação dependentes da sequência e de recursos
Resumo
Este trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas, com tempos de preparação das máquinas dependente da sequência e do número de recursos utilizados. O objetivo do problema é minimizar o tempo total de conclusão das tarefas e número total de recursos utilizados na preparação das máquinas. Dada a complexidade combinatória do problema, propõem-se algoritmos baseados nas metaheurísticas GRASP Reativo e Iterated Local Search (ILS). Os resultados obtidos em cada metaheurística são comparados entre si e com os melhores resultados disponíveis na literatura. Os resultados apresentam o bom desempenho dos algoritmos propostos.Referências
Armentano, V.A. e França Filho, M.F. (2007), “Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory based GRASP approach”. European Journal of Operational Research, 183, 100–114.
Feo, T.A. e Resende, M. (1989), “A probabilistic heuristic for a computationally difficult set covering problem”. Operations Research Letters, 8, 67–71.
Guinet, A. (1991), “Textile production systems: a sucession of non-identical parallel processor shops”. Journal of the Operational Research Society, 42(8): 655-671.
Kim, D-W., Kim, K-H, Jang, W. e Chen, F.F.(2002), “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and Computer Integrated Manufacturing, 18: 223-231.
Laguna, M. e González-Velarde, J.L. (1991), “A search heuristic for just-in-time scheduling in parallel machines”. Journal of Intelligent Manufacturing., 2, 253–260.
Lourenço, H.R.; Martin, O. e Stutzle, T. (2002), “Iterated Local Search”. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 321–353. Kluwer Academic Publishers, Norwell, MA.
Marsh, J.D. e Montgomery, D.C. (1973), “Optimal procedures for scheduling Jobs with sequence-dependent changeover times on parallel processors”. AIIE Technical Papers, 279-286.
Osman, I. e Potts, C. (1989), “Simulated annealing for permutation flow-shop scheduling”. Omega, 17(6), 551–557.
Prais, M. e Ribeiro, C.C. (2000), “Reactive grasp: An application to a matrix decomposition problem in tdma traffic assignment”. INFORMS Journal on Computing, 12(3), 164–176.
Ruiz, R. e Andrés, C. (2007), “Unrelated parallel machines scheduling with resourceassignable sequence dependent setup times”. Em Baptiste, P., Kendall, G., MunierKordon, A., Sourd, F., eds.: Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Paris, France, 439–446.
Ruiz, R. e Stutzle, T. (2008), “An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives”.
European Journal of Operational Research, 187(3), 1143–1159.
Tang, L.X. e Luo, J.X. (2006), “A new ILS algorithm for parallel machine scheduling problems”. Journal of Intelligent Manufacturing., 17(5), 609–619.
Webster, S.T. (1997), “The complexity of scheduling job families about a common date”. Operations Research Letters, 20(2), 65–74.
Feo, T.A. e Resende, M. (1989), “A probabilistic heuristic for a computationally difficult set covering problem”. Operations Research Letters, 8, 67–71.
Guinet, A. (1991), “Textile production systems: a sucession of non-identical parallel processor shops”. Journal of the Operational Research Society, 42(8): 655-671.
Kim, D-W., Kim, K-H, Jang, W. e Chen, F.F.(2002), “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and Computer Integrated Manufacturing, 18: 223-231.
Laguna, M. e González-Velarde, J.L. (1991), “A search heuristic for just-in-time scheduling in parallel machines”. Journal of Intelligent Manufacturing., 2, 253–260.
Lourenço, H.R.; Martin, O. e Stutzle, T. (2002), “Iterated Local Search”. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 321–353. Kluwer Academic Publishers, Norwell, MA.
Marsh, J.D. e Montgomery, D.C. (1973), “Optimal procedures for scheduling Jobs with sequence-dependent changeover times on parallel processors”. AIIE Technical Papers, 279-286.
Osman, I. e Potts, C. (1989), “Simulated annealing for permutation flow-shop scheduling”. Omega, 17(6), 551–557.
Prais, M. e Ribeiro, C.C. (2000), “Reactive grasp: An application to a matrix decomposition problem in tdma traffic assignment”. INFORMS Journal on Computing, 12(3), 164–176.
Ruiz, R. e Andrés, C. (2007), “Unrelated parallel machines scheduling with resourceassignable sequence dependent setup times”. Em Baptiste, P., Kendall, G., MunierKordon, A., Sourd, F., eds.: Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Paris, France, 439–446.
Ruiz, R. e Stutzle, T. (2008), “An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives”.
European Journal of Operational Research, 187(3), 1143–1159.
Tang, L.X. e Luo, J.X. (2006), “A new ILS algorithm for parallel machine scheduling problems”. Journal of Intelligent Manufacturing., 17(5), 609–619.
Webster, S.T. (1997), “The complexity of scheduling job families about a common date”. Operations Research Letters, 20(2), 65–74.
Publicado
19/07/2011
Como Citar
KAMPKE, Edmar Hell; ARROYO, José Elias Cláudio; SANTOS, André Gustavo dos.
GRASP Reativo e Iterated Local Search aplicado ao problema de programação de tarefas em máquinas paralelas com tempos de preparação dependentes da sequência e de recursos. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 8. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 370-381.
ISSN 2763-9061.
