Modern service-based processes in mobile environments are highly complex due to the necessary spatial-temporal coordination between multiple participating users and the consideration of context information. Due to the dynamic nature of mobile environments, disruptive events occur at runtime, which require a re-selection of the planned service compositions respecting multiple users and context-awareness. Thereby, when re-selecting services the features performance, solution quality, solution robustness and alternative solutions are essential and contribute to the efficacy of service systems. This paper presents an optimization-based heuristic technique based on a stateful representation that uses a region-based approach to re-select services considering multiple users, context information and in particular disruptive events at runtime. The evaluation results, which are based on a real-world scenario from the tourism domain, show that the proposed heuristic is superior compared to competing artifacts.