This study applied the approach of minimal cuts for demand to estimate the time-related reliability of a multi-state flow network (MSFN). The maximal capacity vectors that did not meet the demand rate were generated by a proposed algorithm. The Weibull reliability function was adopted to derive the probability distribution for arc capacity in the MSFN. According to the generated d-MCs and derived probability distributions, the MSFN system unreliability was calculated by the recursive sum of the disjoint products. Furthermore, the system reliability was 1-system unreliability, which is a performance index of an MSFN. Based on the system unreliability, a maintenance model with three strategies was proposed to retain the service level of the MSFN. Experimental results show the performance of the proposed maintenance strategies. The advantages of different maintenance strategies are further discussed for managers to determine an appropriate alternative to maintain MSFN capability.