Run-time generation of adaptation plans is a powerful mechanism that helps a self-adaptive system to meet its goals in a dynamically changing environment. In the past, researchers have demonstrated successful use of various automated planning techniques to generate adaptation plans at run time. However, for a planning technique, there is often a trade-off between timeliness and optimality of the solution. For some self-adaptive systems, ideally, one would like to have a planning approach that is both quick and finds an optimal adaptation plan. To find the right balance between these conflicting requirements, this paper introduces a hybrid planning approach that combines more than one planner to obtain the benefits of each. In this paper, to instantiate a hybrid planner we combine deterministic planning with Markov Decision Process (MDP) planning to obtain the best of both worlds: deterministic planning provides plans quickly when timeliness is critical, while allowing MDP planning to generate optimal plans when the system has sufficient time to do so. We validate the hybrid planning approach using a realistic workload pattern in a simulated cloud-based self-adaptive system.