A series of new QoS challenges can be used to pose constraints on workflow schedulers. For this reason, the schedulers sometime cannot generate an optimal schedule based on the available information. Even though many schedulers using various techniques ranging from simple modified approaches to complex algorithms based on task prediction and estimation offer solutions to these challenges. However, those techniques’ performance is degraded when the task information changed or not accurately predicted. This thesis presents the full rescheduling strategy as the enhancement of an existing scheduler to make it more resilient to the changes of task and execution information. The full rescheduling strategy is a scheduling strategy which considers both the running tasks and pending tasks in the queue. The purpose of this enhancement is to allow the scheduler to modify its previous schedule and adjust it accordingly based on the new information. An evaluation of the proposed strategy is done using real-world data and the FCFS with cloud awareness running in the hybrid cloud environment. In this thesis, we validated the scheduler’s behaviors after enhanced with full rescheduling, and discussed the benefits of this strategy in term of costs.