Real-time services have been supported by and large on circuit-switched networks. Recent trends favour services ported on packet-switched networks. For audio conferencing, we need to consider many issues such as scalability, quality of the conference application, floor control and load on the servers. In this paper, we deal with the allocation of Conference Servers (CS) that is part of an audio service framework designed to provide a Virtual Conferencing Environment (VCE). The system is designed to accommodate a large number of end users speaking at the same time and spread across the Internet. The framework is based on conference servers which facilitate audio mixing and distribution. Concurrently, we exploit the Session Initiation Protocol (SIP) capabilities for signaling purposes. We address here the problem of facilitating seamless conference amongst participants using CSs. This demands a proper allocation of CSs to clients to maximise the number of participants served and at a reduced cost. This problem is popularly identified as the Facility Location Problem, a class rich in challenges used to model the minimisation problem of assignment of clients to servers. Seeking a more realistic approach, we avoid over-simplifying assumptions; thus the problem becomes relatively harder. Since these problems are NP-hard, algorithms leading to approximate solutions or those involving heuristics are commonly resorted to. We present heuristic algorithms to solve this class of problems and bring about the effectiveness of their performance.