Nowadays, hybrid cloud platforms stand as an attractive solution for organizations intending to implement combined private and public cloud applications, in order to meet their profitability requirements. However, this can only be achieved through the utilization of available resources while speeding up execution processes. Accordingly, deploying new applications entails dedicating some of these processes to a private cloud solution, while allocating others to the public cloud. In this context, the present work is set to help minimize relevant costs and deliver effective choices for an optimal service placement solution within minimal execution time. Several evolutionary algorithms have been applied to solve the service placement problem and are used when dealing with complex solution spaces to provide an optimal placement and often produce a short execution time. The standard BPSO algorithm is found to display a significant disadvantage, namely, of easily trapping into local optima, in addition to demonstrating a noticeable lack of robustness in dealing with service placement problems. Hence, to overcome critical shortcomings associated with the standard BPSO, an Enhanced Binary Particle Swarm Optimization (E-BPSO) algorithm is proposed, consisting of a modification of the particle position updating equation, initially inspired from the continuous PSO. Our proposed E-BPSO algorithm is shown to outperform state-of-the-art approaches in terms of both cost and execution time, using a real benchmark.