In testing Cloud environment testing tasks requested by different tenants have many uncertainties. The arriving time, deadline and the number of tasks are unknown in advance. Especially, the relationships between testing tasks and testing environments are very complex. How to efficiently manage these tasks is really a challenging problem. This paper studies the special features of testing tasks and presents a task management framework. We analyze the dependencies and conflicts associated with testing tasks and their related runtime environments, using rule matching mechanism to derive the relationships supported by domain knowledge. Based on these analyses, improved algorithms are introduced to cluster and dynamically schedule testing tasks to minimize the make-span or meet deadlines with the consideration of testing task resource requirements and Cloud resource utilization balance at the same time. A fault tolerance mechanism is built to cope with testing errors, whose results are studied to ameliorate clustering and scheduling algorithms. A suite of experiments compares the effectiveness of the proposed approach with other algorithms. © 2011 IEEE.