A class of semi-Markov models, having applications in operations research and reliability engineering, is examined. The special structure of these models permits their analysis by the inspection of flowgraphs having matrix-valued gains on their branches. The use of such flowgraphs effectively reduces the size and complexity of the state space required for analysis, leading to considerable simplification in both formulation and computation. These flowgraph procedures are presented in the context of reliability and availability analysis for systems whose missions are of uncertain duration, but other areas of application are also noted.