Fault tolerant scheduling of many jobs in an environment with millions of unpredictable nodes is not an easy issue. To the best of our knowledge, no work in the literature has proposed a solution that combines the merits of active and passive replication schemes of fault tolerance with the advantages of performance-driven load balancing so as to make the most of the strong points of each. While extensive fault tolerant scheduling and load balancing methods have been presented for the sequential jobs, none have taken into account fault-tolerant load balancing that minimizes the job make-span, provides efficient network and node utilization, achieves a Ill-balanced load and high system flexibility even during the resource failures. Hence, in this article, I present an Adaptive Scheduling Algorithm namely ASA that overcomes these problems. With thorough simulations, I conclude that ASA allocates any number of jobs to a million nodes with relatively low overhead and high flexibility. Experimental results show that the performance of ASA is better than those of its counterparts.