Partitioning of units into multiple groups occurs naturally in multilevel plants where equipment must be distributed onto different floors, so as to minimize material flow costs. A significant complication introduced in multilevel layout is the dependence of the cost of material Bows between units on the relative levels of the respective unit locations. This feature leads to three distinct costs for downward, upward and horizontal flow between any pair of units. In this paper, we formulate this problem as an Integer Non-Linear Program. A heuristic procedure proposed for the single floor graph partitioning problem in Part I of this work is extended to address this problem. Global optima were obtained for all examples for which the exact optimal solutions were obtainable by exhaustive enumeration. Solutions for problems with up to 70 units were obtained in reasonable computation times, suggesting applicability of the procedure to chemical plants of realistic scope. Additionally, a linearization scheme is used to convert the INLP to an MILP. Continuous relaxations of the MILP are solved by Lagrangean Relaxation and Subgradient Optimization to yield good lower bounds. It is demonstrated that the linearization is sufficiently tight that, for some problem instances, solutions to the continuous relaxation are optimal. In general, the combination of upper and lower bounding procedures is effective as a means of both obtaining good solutions and estimating the deviation from the optimal solution for problems of practical scope.