Proposta de análise de desempenho de algoritmos para otimização de redes
de filas M/G/c/K baseada em DOE

Barbosa, Helinton André L.; Caldas, Gabriel Bahia; Cruz, Frederico Rodrigues B. da

doi:10.1590/S0103-65132013005000043

Article

Proposta de análise de desempenho de algoritmos para otimização de redes de filas M/G/c/K baseada em DOE

A DOE-based proposal for performance analysis of M/G/c/K queueing network optimization algoritms

Barbosa, Helinton André L.; Caldas, Gabriel Bahia; Cruz, Frederico Rodrigues B. da

http://dx.doi.org/10.1590/S0103-65132013005000043 Production, vol.24, n1, p.13-25, 2014

PDF

Downloads: 0

Resumo

Neste artigo são apresentados resultados da análise empírica de um algoritmo proposto na literatura para alocação de áreas de espera em redes de filas finitas, abertas e acíclicas, com serviços gerais e servidores múltiplos. Dos resultados computacionais é concluído que o tempo de processamento do algoritmo depende do número de servidores da rede, como era de se esperar, mas independe do quadrado do coeficiente de variação do tempo de serviço. Conclui-se também que as alocações obtidas são robustas e que, em geral, o desempenho global previsto para a rede é acurado, conforme atestado por simulações. Finalmente, chega-se à conclusão de que não é fácil encontrar regras heurísticas para o posicionamento dos servidores múltiplos na rede de filas sem aplicar um algoritmo de alocação de áreas de espera para determinar qual configuração é a melhor.

Palavras-chave

Otimização. Avaliação de desempenho. Processos estocásticos. Delineamento de experimentos.

Abstract

This paper presents the results of an empirical analysis of a previously proposed algorithm for buffer allocation in finite open acyclic general-service multi-server queuing networks. Based on the computational results, it is concluded that the processing time of the algorithm depends on the number of network servers (as expected) but is independent of the squared coefficient of variation of service time. It is also concluded that the obtained allocations are robust and that the approximations for the performance measures are accurate, as verified by simulation. Finally, it is found that it is not straightforward to develop heuristic rules to allocate multiple servers in the topology without applying a buffer allocation algorithm to determine the optimal configuration.

Keywords

Optimization. Performance evaluation. Stochastic process. Design of experiments.

References

ANDRIANSYAH, R. et al. Performance optimization of open zero-buffer multi-server queueing networks. Computers & Operations Research, v. 37, n. 8, p. 1472-1487, 2010. http://dx.doi.org/10.1016/j.cor.2009.11.004

ARGOUD, A. R. T. T.; GONÇALVES FILHO, E. V.; TIBERTI, A. J. Algoritmo genético de agrupamento para formação de módulos de arranjo físico. Gestão & Produção, v. 15, n. 2, p. 393-405, 2008. http://dx.doi.org/10.1590/ S0104-530X2008000200014

BAZARAA, M. S.; SHERALI, H. D.; SHETTY, C. M. Nonlinear Programming: Theory and Algorithms. 3rd ed. New York: Wiley-Interscience, 2006. p. 872.

BITRAN, G. R.; MORABITO, R. An overview of tradeoff curve analysis in the design of manufacturing systems. Gestão & Produção, v. 3, n. 2, p. 108-134, 1996. http://dx.doi. org/10.1590/S0104-530X1996000200001

BITRAN, G. R.; MORABITO, R. Um exame dos modelos de redes de filas abertas aplicados a sistemas de manufatura discretos: Parte II. Gestão & Produção, v. 2, n. 3, p. 297-321, 1995. http://dx.doi.org/10.1590/S0104- 530X1995000300005

CRUZ, F. R. B.; VAN WOENSEL, T.; SMITH, J. M. Buffer and throughput trade-offs in M/G/1/K queueing networks: A bi-criteria approach. International Journal of Production Economics, v. 125, n. 2, p. 224-234, 2010. http://dx.doi. org/10.1016/j.ijpe.2010.02.017

DOY, F. E. et al. Simulação do serviço de correio eletrônico através de um modelo de filas. Pesquisa Operacional, v. 26, n. 2, p. 241-253, 2006.

GROSS, D. et al. Fundamentals of queueing theory. 4th ed. New York: Wiley-Interscience, 2009. p. 600.

HSU, J. Multiple comparisons: Theory and methods. Boca Raton: Chapman and Hall/CRC, 1996. p. 296.

IANNONI, A. P.; MORABITO, R. Modelo de fila hipercubo com múltiplo despacho e backup parcial para análise de sistemas de atendimento médico emergenciais em rodovias. Pesquisa Operacional, v. 26, n. 3, p. 493-519, 2006. http://dx.doi.org/10.1590/S0101- 74382006000300004

IANNONI, A. P.; MORABITO, R. Otimização da localização das bases de ambulâncias e do dimensionamento das suas regiões de cobertura em rodovias. Produção, v. 18, n. 1, p. 47-63, 2008. http://dx.doi.org/10.1590/S0103- 65132008000100004

KENDALL, D. G. Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains. Annals of Mathematical Statistics, v. 24, p. 338-354, 1953. http://dx.doi.org/10.1214/ aoms/1177728975

KERBACHE, L.; SMITH, J. M. The generalized expansion method for open finite queueing networks. European Journal of Operational Research, v. 32, p. 448-461, 1987. http://dx.doi.org/10.1016/S0377-2217(87)80012-7

KIMURA, T. A transform-free approximation for the finite capacity M/G/s queue. Operations Research, v. 44, n. 6, p. 984-988, 1996. http://dx.doi.org/10.1287/ opre.44.6.984

KLEINROCK, L. Queueing Systems. New York: John Wiley & Sons, 1975. v. I: Theory, p. 417.

LABETOULLE, J.; PUJOLLE, G. Isolation method in a network of queues. IEEE Transactions on Software Engineering, v. 6, n. 4, p. 373-380, 1980. http://dx.doi.org/10.1109/

TSE.1980.234493

LEMARÉCHAL, C. The omnipresence of Lagrange. Annals of Operations Research, v. 153, n. 1, p. 9-27, 2007. http:// dx.doi.org/10.1007/s10479-007-0169-1

MIGUEL, P. A. C. (Org.). Metodologia de pesquisa em engenharia de produção e gestão de operações. Rio de Janeiro: Elsevier, 2010. p. 226.

MINITAB INC. Minitab Statistical Software, Release 15 for Windows. Pennsylvania: State College, 2006. Minitab® is a registered trademark of Minitab Inc.

MONTGOMERY, D. C. Design and Analysis of Experiments. 7. ed. New York: John Wiley & Sons, 2008. p. 680.

MORABITO, R.; LIMA, F. C. R. Um modelo para analisar o problema de filas em caixas de supermercados: um estudo de caso. Pesquisa Operacional, v. 20, n. 1, p. 59- 71, 2000.

SELLITTO, M. A.; BORCHARDT, M.; PEREIRA, G. M. Medição de tempo de atravessamento e inventário em processo em manufatura controlada por ordens de fabricação. Produção, v. 18, n. 3, p. 493-507, 2008.

SILVA, C. R. N.; MORABITO, R. Análise de problemas de partição de instalações em sistemas job-shops por meio de modelos de redes de filas. Pesquisa Operacional, v. 27, n. 2, p. 333-356, 2007a. http://dx.doi.org/10.1590/ S0101-74382007000200008

SILVA, C. R. N.; MORABITO, R. Aplicação de modelos de redes de filas abertas no planejamento do sistema job-shop de uma planta metal-mecânica. Gestão & Produção, v. 14, n. 2, p. 393-410, 2007b.

SMITH, J. M. M/G/c/K blocking probability models and system performance. Performance Evaluation, v. 52, n. 4, p. 237-267, 2003. http://dx.doi.org/10.1016/S0166- 5316(02)00190-6

SMITH, J. M.; CRUZ, F. R. B. The buffer allocation problem for general finite buffer queueing networks. IIE Transactions on Design & Manufacturing, v. 37, n. 4, p. 343-365, 2005.

SMITH, J. M.; CRUZ, F. R. B.; VAN WOENSEL, T. Topological network design of general, finite, multi-server queueing networks. European Journal of Operational Research, v. 201, n. 2, p. 427-441, 2010. http://dx.doi. org/10.1016/j.ejor.2009.03.012

SPINELLIS, D.; PAPADOULOS, C. T.; SMITH, J. M. Large production line optimization using simulated annealing. International Journal of Production Research, v. 38, n. 3, p. 509-541, 2000. http://dx.doi. org/10.1080/002075400189284

TAKEDA, R. A.; WIDMER, J. A.; MORABITO, R. Aplicação do modelo hipercubo de filas para avaliar a descentralização de ambulâncias em um sistema urbano de atendimento médico de urgência. Pesquisa Operacional, v. 24, n. 1, p. 39-71, 2004.

YANASSE, H. H.; BECCENERI, J. C.; SOMA, N. Y. Um algoritmo exato com ordenamento parcial para solução de um problema de programação da produção: experimentos computacionais. Gestão & Produção, v. 14, n. 2, p. 353- 361, 2007.