Numerical analysis of minimum cost network flow with queuing stations: the M/M/1 case


network flow
supply chain
queueing networks
cycle time
work in process flujo en redes
cadena de abasto
redes de colas
tiempo de ciclo
trabajo en proceso

How to Cite

Hernández-González, S., Flores-de-la-Mota, I., Jiménez-García, J. A., & Hernández-Ripalda, M. D. (2017). Numerical analysis of minimum cost network flow with queuing stations: the M/M/1 case. Nova Scientia, 9(18), 257–289.


In a network the nodes represent stations, warehouses, distribution centers and customers and not just materials but also information circulate, so the minimum cost flow model, that only takes transport costs into account is one of the tools used to support the decision-making. In reality, the nodes provide a service which requires a service time, the servicing follows a discipline and also a queue is formed, generating the respective service and queuing costs. A modified version of the minimum cost flow model is proposed in this paper for the optimization of the flow in a queuing network. A variety of cases were solved. An acceptable level of accuracy was observed in the calculation of the time cycle and work in progress. The results indicate that the optimum solution tends to balance the workload along the network. This paper is of interest to administrators and people in charge of supply chains and is useful for decision-making in the medium or long time.


Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (1974) Linear programming and network flows. Wiley 4th ed.

Beard, J.C. and Chamberlain, R.D.(2013) Analysis of a simple approach to modeling perfor-mance for streaming data applications. Proc. of IEEE 21st International Symposium on Mod-elling, Analysis & Simulation of Computer and Telecommunication Systems, 345 – 359.

Bhaskar, V. and Lallement, P.(2010) Modeling a supply chain using a network of queues. Applied Mathematical Modelling, 34 (8). 2074 – 2088.

Bolch, G., Greiner, S., de Meer, H. and Trivedi, Kishor S. (2006) Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. 2nd edition. Berlín. Wiley-Interscience.

Buzacott, J., and Shanthikumar, G. (1993) Stochastic models of manufacturing systems. Up-per Saddle River: Prentice Hall. New York.

Curry, G. and Feldman, F.M. (2011). Manufacturing systems. Springer. Berlín.

He, X. and Hu, W. (2014) Modeling Relief Demands in an Emergency Supply Chain System under Large-Scale Disasters Based on a Queuing Network. The Scientific World Journal, 2014. 1 – 12.

Kerbache, L. and MacGregor Smith, J. (2000) Multi-objective routing within large scale facil-ities using open finite queueing networks. European Journal of Operational Research, 121 (1). 105 – 123.

Lawrence, S.R. and Buss, A.H. (1995) Economic analysis of production bottleneck. Mathe-matical Problems in Engineering, 1(1). 341 – 363.

MacGregor Smith, J., Daskalaki, S. (1988) Buffer space allocation in automated assembly lines. Operations Research, 36(2), 343 – 358.

MacGregor Smith, J. (2011) Optimal routing in closing queueing networks with state depend-ent queues. INFOR: Information Systems and Operational Research, 49(1). 45 – 62.

Morabito, R., de Souza, M.C. and Vazquez, M.(2014) Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queueing networks. European Journal of Operational Research, 232 (3). 618 – 629.

Pourbabai, B., Blanc J.P.C., van der Duyn Schouten, F.A. (1996) Optimizing flow rates in a queueing network with side constraints. European Journal of Operational Research, 88 (3). 586 – 591.

Srinivasa N.R., Viswanadham, N. (2001) Generalized queueing networks analysis of inte-grated supply chains. International Journal of Production Research, 39(2), 205 – 224.

Srivathsan, S. and Kamath, M. (2012) An Analytical Performance Modeling Approach for Supply Chain Networks. IEEE Transactions on Automation Science and Engineering, 9(2). 265 – 275.

van Woensel T., Cruz F.R.B. (2014) Optimal Routing in General Finite Multi-Server Queueing Networks. PLoS ONE 9(7): e102075. doi:10.1371/journal.pone.0102075

Wagner, H.M. (1975) Principles of Operations Research, with Applications to Managerial Decisions. Prentice Hall. New York.

Yenisey, M.M. (2006) A flow-network approach for equilibrium of material requirements planning. International Journal of Production Economics 102, 317 – 332.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2017 Nova Scientia