This article presents a new parallel hybrid evolutionary algorithm to solve the problem of virtual machines subletting in cloud systems. The problem deals with the efficient allocation of a set of virtual machine requests from customers into available pre-booked resources from a cloud broker, in order to maximize the broker profit. The proposed parallel algorithm uses a distributed subpopulations model, and a Simulated Annealing operator. The experimental evaluation analyzes the profit and make span results of the proposed methods over a set of problem instances that account for realistic workloads and scenarios using real data from cloud providers. A comparison with greedy heuristics indicates that the proposed method is able to compute solutions with up to 133.8% improvement in the profit values, while accounting for accurate make span results.