Cloud computing is increasingly becoming a mainstream technology-delivery model from which companies and research aim to gain value. As different cloud providers offer cloud services in various forms, there is a huge potential of optimizing the selection of those services to better fulfill user-, i.e., consumer- and application-related requirements. Recently, multi-cloud environments have been introduced thus making it possible to execute applications not only on single-provider resources, but also by using resources from multiple cloud providers. Due to the growing complexity in cloud marketplaces, a cloud brokerage mechanism, interacting on behalf of the consumers with various cloud providers, can be used to provide decision support for consumers. In this paper, we address the Cloud Resource Management Problem in multi-cloud environments that is a recent optimization problem aimed at reducing the monetary cost and the execution time of consumer applications using Infrastructure as a Service of multiple cloud providers. Due to the fact that consumers require real-time and high-quality solutions to economically automate cloud resource management and corresponding deployment processes, we propose an efficient Biased Random-Key Genetic Algorithm. The computational experiments over a large benchmark suite generated based on real cloud market resources indicate that the performance of our approach outperforms the approaches proposed in the literature.