A note on a generalized network flow model for manufacturing process

Manufacturing network flow (MNF) is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem. Supported by the National Natural Science Foundation of China (No. 10371028, No. 10671177), the Key Project of Chinese Ministry of Education (No. 1080607), the Scientific Research Grant of Jiangnan University (No. 314000-52210382), and the Youth Foundation from School of Science of Jiangnan University (January 2008-December 2009).