GRASP reativo aplicado ao problema de programação de tarefas em máquinas paralelas com tempos de preparação dependente da seqüência e de recursos
Resumo
Este trabalho aborda o problema de seqüenciamento de tarefas em máquinas paralelas, com tempos de preparação das máquinas dependente da seqüê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õe-se um algoritmo baseado na heurística GRASP no qual o parâmetro de aleatoriedade utilizado na fase de construção é auto-ajustado de acordo com as soluções previamente encontradas (GRASP reativo). Os resultados obtidos são comparados com os melhores resultados disponíveis na literatura e mostram o bom desempenho do algoritmo proposto.
Referências
Aiex, R.M., Binato, S. e Resende, M.G.C. (2003), “Parallel GRASP with path-relinking for job shop scheduling”. Parallel Computing, 29:393–430.
Armentano, V.A. e Yamashita, D.S. (2000), “Tabu search for scheduling on identical parallel machines to minimize mean tardiness”. J Intell Manuf. 11:453–460.
Feo, T.A. e Resende, M.G.C. (1995), “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6, 109-133.
Feo, T.A., Sarathy, K. e McGahan, J. (1996), “A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties”. Computers & Operations Research, 23:881-895.
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.
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.
Prais, M. e Ribeiro, C. (2000), “Reactive GRASP: na application to a matrix decomposition problem in TDMA traffic assignment”. INFORMS Journal on Computing, 12(3):164-176.
Ruiz, R. e Andrés, C. (2006), “Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times”. MISTA Conference, 3, 439-446.
Armentano, V.A. e Yamashita, D.S. (2000), “Tabu search for scheduling on identical parallel machines to minimize mean tardiness”. J Intell Manuf. 11:453–460.
Feo, T.A. e Resende, M.G.C. (1995), “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6, 109-133.
Feo, T.A., Sarathy, K. e McGahan, J. (1996), “A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties”. Computers & Operations Research, 23:881-895.
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.
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.
Prais, M. e Ribeiro, C. (2000), “Reactive GRASP: na application to a matrix decomposition problem in TDMA traffic assignment”. INFORMS Journal on Computing, 12(3):164-176.
Ruiz, R. e Andrés, C. (2006), “Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times”. MISTA Conference, 3, 439-446.
Publicado
20/07/2009
Como Citar
KAMPKE, Edmar Hell; ARROYO, José Elias Cláudio; ROCHA, Mauro Nacif.
GRASP reativo aplicado ao problema de programação de tarefas em máquinas paralelas com tempos de preparação dependente da seqüência e de recursos. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 7. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 222-231.
ISSN 2763-9061.
