Abstract
Fang and Qi (Optim. Methods Softw. 18:143–165, 2003) introduced a new generalized network flow model called manufacturing network flow model for manufacturing process modeling. A key distinguishing feature of such models is the assembling of component raw-materials, in a given proportion, into an end-product. This assembling operation cannot be modeled using usual generalized networks (which allow gains and losses in flows), or using multi-commodity networks (which allow flows of multiple commodity types on a single arc). The authors developed a network-simplex-based algorithm to solve a minimum cost flow problem formulated on such a generalized network and indicated systems of linear equations that need to be solved during the course of the network-simplex-based solution procedure. In this paper, it is first shown how various steps of the network-simplex-based solution procedure can be performed efficiently using appropriate data structures. Further, it is also shown how the resulting system of linear equations can be solved directly on the generalized network.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice-Hall, New Jersey
Bazaraa MS, Jarvis JJ, Sherali HD (1990) Linear programming and network flows. Wiley, New York
Fang SC, Qi L (2003) Manufacturing network flows: a generalized network flow model for manufacturing process modeling. Optim Methods Softw 18:143–165
Geoffrion AM, Graves G (1974) Multicommodity distribution system design by Benders’ decomposition. Manag Sci 5:822–854
Glover F, Klingman D, Stulz J (1974) Extensions of the augmented predecessor index method to generalized network problems. Transp Sci 7:377–384
Golden BL, Liberatore M, Lieberman C (1979) Models and solution techniques for cash flow management. Comput Oper Res 6:13–20
Johnson E (1966) Networks and basic solutions. Oper Res 14:89–95
Kennington JL, Helgason RV (1980) Algorithms for network programming. Wiley, New York
Lu H, Yao E, Qi L (2006) Some further results on minimum distribution cost flow problems. J Comb Optim 11:351–371
Mo J, Qi L, Wei Z (2005) A network simplex algorithm for simple manufacturing network model. J Ind Manag Optim 1:251–273
Toth P, Vigo D (eds) (2002) The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelphia
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Venkateshan, P., Mathur, K. & Ballou, R.H. An efficient generalized network-simplex-based algorithm for manufacturing network flows. J Comb Optim 15, 315–341 (2008). https://doi.org/10.1007/s10878-007-9080-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-007-9080-6