One of the key issues in the design of scalable and cost-effective Distributed Virtual Environment systems is the partitioning problem. It consists of efficiently assigning clients (3-D avatars) to the servers in the system, and some proposed methods allow to significantly increase system throughput. However, these methods are not focused on satisfying any specific time constraint.In this paper, we show that the problem of providing quality of service in Distributed Virtual Environment systems can be addressed by means of the partitioning method. Additionally, we propose a partitioning method that not only provides a high system throughput, but it also satisfies (if possible) any time constraint that avatars can require. This method is based on a heuristic search technique that looks for the best trade-off between system latency, system throughput and partitioning efficiency. The evaluation results show that this partitioning method allows to greatly increase the number of avatars provided with quality of service while also providing the highest system throughput as possible.