To solve the dual challenges of uncertain quality of service (QoS) attributes and urgent task disturbances in cloud manufacturing service composition optimization, the interval method is employed to describe the uncertainty of QoS attributes. Then, an interval multi-objective service recomposition optimization model consisting of two sub-models is established. To target the interval-number characteristics in both the objective functions and constraints of the model, a reinforcement learning-based interval fast non-dominated sorting genetic algorithm (RINSGA-II) is proposed. In the RINSGA-II, a hybrid initialization strategy based on multiple heuristic rules is designed to enhance the quality of the initial solution set and accelerate convergence. Additionally, an interval Pareto dominance and crowding distance calculation method incorporating interval arithmetic is employed to compare solution quality precisely. To balance the algorithm’s global exploration and local exploitation capabilities, an adaptive parameter adjustment strategy based on Q-learning is developed. Finally, simulation experiments are conducted using problem instances of varying scales. The experimental results show that the RINSGA-II significantly outperforms comparative algorithms in terms of the convergence and diversity of the optimal solution set, and it can generate constraint-satisfying and robust service composition schemes.