Maximum Flow Problem in Assembly Manufacturing Networks

In this dissertation, we study a maximum flow problem with one single output based on the capacitated assembly manufacturing network flow structure. In such a network flow problem, combination nodes are used to model the assembly processes where resources and/or semifinished products are mixed proportionally. A network simplex algorithm for assembly manufacturing network flows with the flow balance equation on every node has been investigated in the literature. However, the problem becomes more complicated when capacity constraints are involved and the flow balance equation no longer holds at the combination nodes. We formulate the capacitated maximum assembly manufacturing flow problem in a standard form and propose an algorithm for finding the maximum output flow. The proposed network simplex algorithm emphasizes the analysis of the network structures inside the basic feasible graph and pivoting graph. We evaluate the complexities of the two types of pivoting with graph decomposition techniques and design specific treatments to reduce the theoretical computation requirement. The proposed algorithm runs faster than the Simplex solver from MATLAB in low dimension experimental instance with various amount of C nodes. In the medium and large dimension instances, our algorithm consumes more time than the Simplex if there is not sufficient adjacent arcs of C nodes in the network. When the average number of incoming arcs for each C node gets higher in the medium and large dimension instances, our algorithm starts performing better than the Simplex solver in terms of the computation time.