This paper proposes a Mixed Integer Non Linear Programming (MINLP) model and two-stage optimization algorithm for determining the most profitable synthesis and design of Combined Heat and Power units within a district heating network with heat storage while taking into account the optimal scheduling of the units over the year. A two-stage algorithm for tackling the challenging MINLP problem is devised: at the upper level the selection and sizing of the units is optimized by means of specifically selected evolutionary algorithms, while at the lower level the operational scheduling problem is linearized and optimized with a commercial Mixed Integer Linear Programing solver. Three different approaches, based on two different evolutionary algorithms and discrete variable relaxation, are devised and compared to tackle the upper level problem. Moreover a bounding technique is proposed to limit the computational time required to solve the lower-level problem. The overall algorithm is tested on an industrial scale problem to find the two system designs leading to the minimum energy consumption and the minimum total annual cost. Computational results indicate that the continuous relaxation of the plant sizes significantly helps to improve the convergence rate of the tested evolutionary algorithm and to find improved solutions. For the considered test case, the design optimized for the minimum energy consumption allows to save 64% of primary energy compared to the minimum total annual cost solution, but with a 28% higher total annual cost. (C) 2017 Elsevier Ltd. All rights reserved.