Análise de um algoritmo aproximativo para o problema de escalonamento de tarefas com restrições de precedência em máquinas paralelas idênticas
Resumo
Neste artigo é apresentado o problema de escalonamento de tarefas com tempos de execução unitários e restrições de precedência, considerando um número variável de máquinas paralelas idênticas, que é NP-difícil. Para este problema, a melhor razão de aproximação era fornecida pelo algoritmo de Coffman e Graham (1972), de fator de aproximação 2 − 2/m, para m ≥ 3 máquinas paralelas idênticas, e que perdurou por um longo tempo até que recentemente um algoritmo de fator de aproximação 2 − 7/3m+1 foi proposto por Gangal e Ranade (2008), proporcionando uma melhoria pequena mas significativa e com conceitos teóricos interessantes, cuja análise é apresentada.
Referências
Braschi, B. and Trystram, D. (1994). A new insight into the coffman-graham algorithm. SIAM J. Comput., 23:662–669.
Coffman, E. and Graham, R. (1972). Optimal Scheduling of coffman-graham algorithm for a new order class. Acta informatica, 1:200-213.
Feng, T., editor (1975). Parallel Processing, Proceedings of the Sagamore Computer Conference, August 20-23, 1974, volume 24 of Lecture Notes in Computer Science. Springer.
Gangal, D. and Ranade., A. (2008). Precedence constrained scheduling in (2 − 7 3p+1) para p 4 optimal. Elsevier. Journal of Computer and System Sciences, 74 (2008) 1139-1146., Vol:1:1–13.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics.
Hu, T. C. (1961). Parallel sequencing and assembly line problems. IBM Research Center, Yorktotim, New York, 1(1):8.
Papadimitriou, C. and Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAN J. Comput., 8(3): 405-409.
Ullman, J. (1975). Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393.
Coffman, E. and Graham, R. (1972). Optimal Scheduling of coffman-graham algorithm for a new order class. Acta informatica, 1:200-213.
Feng, T., editor (1975). Parallel Processing, Proceedings of the Sagamore Computer Conference, August 20-23, 1974, volume 24 of Lecture Notes in Computer Science. Springer.
Gangal, D. and Ranade., A. (2008). Precedence constrained scheduling in (2 − 7 3p+1) para p 4 optimal. Elsevier. Journal of Computer and System Sciences, 74 (2008) 1139-1146., Vol:1:1–13.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics.
Hu, T. C. (1961). Parallel sequencing and assembly line problems. IBM Research Center, Yorktotim, New York, 1(1):8.
Papadimitriou, C. and Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAN J. Comput., 8(3): 405-409.
Ullman, J. (1975). Np-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384–393.
Publicado
04/07/2016
Como Citar
LEVER, Elton; VILCA, Omar; DE FREITAS, Rosiane.
Análise de um algoritmo aproximativo para o problema de escalonamento de tarefas com restrições de precedência em máquinas paralelas idênticas. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 808-811.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9830.
