Resource provisioning is a key issue in large-scale distributed systems such as cloud computing systems. Several resource provider systems utilized preemptive resource allocation techniques to maintain a high quality of service level. When there is a lack of resources for high-priority requests, leases/jobs with higher priority can run by suspending or canceling leases/jobs with lower priority to release the required resources. The state-of-the-art preemptive resource allocation methods are classified into two classes, namely, (1) heuristic and (2) brute force. The heuristic-based methods are fast, but they can’t maintain the system performance, while brute force-based methods are vice versa. In this work, we proposed a new multi-objective preemptive resource allocation policy that benefits from these two classes. We proposed a new heuristic called Best K-First-Fit (Best-KFF). The Best-KFF searches for the first k preemption choices at each physical machine (PM) and then sorts these preemption choices obtained from the PMs with respect to several objectives (e.g., resource utilization). Then, the Best-KFF selects the best choice maintaining the cloud computing system performance. Thus, the Best-KFF algorithm is a compromise between the heuristic and brute force classes. The higher the value of k is, the larger the search space is. The Best-KFF method maximizes the resource utilization of the physical machines and minimizes the average waiting time of advanced-reservation requests, the number of lease preemption, the preemption time, and energy consumption. The proposed method was thoroughly examined and compared against the state-of-the-art methods. The experimental results on various cloud computing systems demonstrated that the proposed preemption policy outperforms the state-of-the-art methods.