PARTITIONING AND TEARING OF NETWORKS - APPLIED TO PROCESS FLOWSHEETING

A review of the methods available for identification of the computational sequence in modular process simulators (partitioning and tearing) is followed by the presentation of a new very efficient and close-to-optimal routine for tearing. While partitioning is simple and straightforward, tearing belongs to the class of problems that are stated to be NP-complete (Karp) and thus computationally intractable. A new and very simple method for the weighted case of tearing is presented which may serve as an upper bound algorithm in a branch and bound strategy. It is based on repeated application of a partitioning procedure such as Johns' or Tarjan's routine. Between each partitioning, all input streams to a selected vertex are removed from the graph (torn). The algorithm has been run on 10 test problems and executes slightly faster than 0(n**2) with a very small constant factor.