Central Office (CO) maintenance is becoming a major overhead for backbone service providers. Trunk to Switch Assignment (TSA) problem is seen as a crucial problem in maintenance of a Central Office. In this paper we formulate the TSA problem as a set partitioning problem and present an efficient heuristic search algorithm BDFS (Block Depth First Search) for minimizing switching overhead in Central Offices. To guide this algorithm, we have developed a new lower bound function, based on relaxation of the problem of merging external trunks into switches. We used the lower bound admissible heuristic (H-III) along with the proposed technique to solve this problem. While comparing the performance of BDFS, we have found that BDFS outperforms IDA* on various performance metrics. We have also suggested a real-time version of BDFS algorithm that gives high quality sub-optimal or optimal solution with a user specified time. Real-time BDFS gives optimal solution within 50-60% of the total execution time for most of the problem instances. The Real-time BDFS can be used to optimize the existing configurations with minimal changes and can also help service providers in taking quick decisions before making a detailed study regarding planning requirements.