This paper describes the simultaneous optimization of process flowsheets and their heat exchanger networks (HENs) using rigorous models and detailed cost functions. An optimization procedure is proposed by which tradeoffs between operating plus capital costs of a process and utility plus capital costs of their heat integrated HENs are simultaneously taken into account. The procedure relies on a direct search optimization method to reduce the effects of nonconvexities and to enable real large-scale industrial problems with a large number of streams to be solved. A special match-dependent cost targeting formula for HEN is introduced to adjust HEN capital costs to different construction characteristics. A Discrete Complex Algorithm (DCA) is proposed for direct search optimization in a reduced feasible region defined over sets of discretized decision variables. The direct search results in a final HEN design. A simple, yet very robust, nonlinear programming (NLP) optimization model is developed to design HEN with practically any number of streams using the same capital cost function for HEN as in the direct search. The whole optimization procedure is illustrated by the optimization of an existing large-scale chemical process at increasing levels of simultaneity ranging from the sequential to the simultaneous HEN optimization.