In the cloud manufacturing environment, manufacturing resources and capabilities are encapsulated in the form of services. Different tasks are collected to the cloud platform via the cloud and corresponding services are assigned to each task through appropriate scheduling. Due to the uncertainty in task execution, emergency can take place, forcing the remaining tasks to be rescheduled. In addition, the complexity and diversity of tasks in the cloud manufacturing environment will lead to difficulty in finding the optimal solution within a reasonable time period. With the maximum completion time of all the tasks as the optimization goal, a metaheuristic algorithm that combines an improved genetic algorithm and the neighborhood search technique is proposed to tackle the rescheduling caused by the uncertainty of tasks and resource services in the cloud manufacturing environment. The experimental results show that the proposed algorithm can deal with the rescheduling during dynamic scheduling and obtain the optimal solution quickly.