<p>Cloud computing provides scalable and cost-effective access to shared resources through virtualization and distributed systems. With the rapid growth of cloud services, diverse workloads are increasingly submitted to virtual machines (VMs) with heterogeneous capabilities, making efficient task scheduling essential. Inefficient scheduling can cause underutilization, increased latency, task rejection, and service-level agreement (SLA) violations, underscoring the need for adaptive, fault-tolerant, and deadline-aware scheduling mechanisms. This article introduces the <i>Balanced Independent-Task Assignment</i> (<i>BITA</i>) algorithm and its variant <i>BITAr</i> for efficient and fault-tolerant scheduling of independent tasks on cloud-based VMs. <i>BITA</i> addresses soft real-time scheduling through a criticality-driven metric that evaluates task deadlines and VM qualifications for adaptive assignments, reducing task rejection and strengthening fault tolerance. <i>BITAr</i> extends this approach to hard real-time scenarios with strict deadline constraints, prioritizing the utilization of qualified VMs at task arrival. Both algorithms aim to balance workloads, minimize task rejection, enhance fault tolerance, and optimize VM utilization. Experimental results show that <i>BITA</i> and <i>BITAr</i> outperform state-of-the-art methods, achieving higher mean effective utilization (MEU) and lower task rejection rates (TRR) with lower-bound running-time complexity. These findings confirm their scalability and suitability for real-world heterogeneous cloud deployments, improving overall resource efficiency and service reliability.</p>