Business process modeling is a well established methodology for analyzing and optimizing complex processes. To address critical challenges in ubiquitous black-box approaches, we develop a two-stage business process optimization framework. The first stage is based on an analytical approach that exploits structural properties of the underlying stochastic network and renders a near-optimal solution. Starting from this candidate solution, the second stage employs advanced simulation optimization to locally search for optimal business process solutions. Numerical experiments demonstrate the efficacy of our approach. © 2013 IEEE.