The profitability of a chemical plant is directly related to its reliability, which has always been a major concern in the chemical industry. In this paper, we address the problem at the conceptual design phase of an air separation plant to minimize the negative income, which consists of the penalty incurred from pipeline supply interruption and the cost of increasing reliability, including having redundant units and storage tanks. A mixed integer linear programming (MILP) model (denoted as RST) based on the Markov Chain assumption is proposed and applied to the motivating example of an air separation plant. Furthermore, to tackle larger superstructures, we propose a game theoretic algorithm that decomposes and restructures the problem as a team game of the individual processing stages and arrives at a Nash Equilibrium among them. It is also shown that a good initialization point close to the global optimum can be easily obtained, which guarantees the quality of the Nash Equilibrium solution. A number of examples are shown to illustrate the proposed algorithm's ability to solve to global optimality in much shorter time than the direct solution of the original MILP model (RST).