Hardware failures in autonomous and distributed soft- ware systems create the need for self-healing activities. This work addresses the problem of redeploying software compo- nents affected by a hardware failure, while respecting sev- eral runtime constraints. In contrast to existing approaches, we do not only compute a new feasible system configura- tion, but make use of AI planning in order to derive a se- quence of concrete deployment and undeployment actions that achieve this state. We also distinguish between ap- plication of every intermediate plan found and the single application of the final plan. These two plan application strategies are described and evaluated along with our novel solution approach.