We consider a location-inventory optimization model for supply chain (SC) configuration. It includes a supplier, multiple distribution centers (DCs), and multiple retailers. Customer demand and replenishment lead time are considered to be stochastic. Two classes of customer orders, priority and ordinary, are assumed based on their demand. The goal is to find the optimal locations for DCs and their inventory policy simultaneously. For this purpose, a two-phase approach based on queuing theory and stochastic optimization was developed. In the first phase, the stock level of DCs is modeled as a Markov chain process and is analyzed, while in the second phase, a mathematical program is used to determine the optimal number and locations of DCs, the assignment of retailers to DCs, and the order quantity and safety stock level at DCs. As solving this problem is NP-hard, a hybrid Genetic Algorithm (GA) was developed to make the problem computationally tractable.