The IEEE 802.16 standard specifies a MeSH mode which permits the deployment of Wireless Mesh Networks (WMNs) supporting carrier-grade QoS. The network operator for such planned WMNs is interested in maximizing the traffic admitted in the WMN and simultaneously supporting QoS. Recently network coding has emerged as a promising technique for increasing the throughput in WMNs. This paper proposes CORE, which addresses the problem of jointly optimizing the routing, scheduling, and bandwidth savings via network coding. Prior solutions are either not applicable in the 802.16 MeSH or computationally too costly to be of practical use in the WMN under realistic scenarios. COREpsilas heuristics, in contrast, are able to compute solutions for the above problem within a operator definable maximum computational cost, thereby enabling the computation and near real-time deployment of the computed solutions. We analyze the performance of COREpsilas heuristics via a thorough simulation study covering the typical usage scenarios for WMNs. The results presented demonstrate that CORE is able to increase the number of flows admitted considerably and with minimal computational costs. Further, the results provide insights into limiting factors for the gains which can be obtained in different usage scenarios.