Cloud computing infrastructures in contemporary times were very dependent upon effective task scheduling, smart workload management, and proper VM allocation for offering reliable, high-performance computing services and at the same time achieving optimal operational cost, energy footprint, and physical data centre utilization. Since multi-processor job scheduling among heterogeneous distributed processing nodes is an NP-hard problem of combinatorial optimization without any polynomial-time solution, cloud management systems will be required to use heuristic, meta-heuristic, and hybrid approximation approaches to find nearly optimal mappings of tasks onto the available resources within finite time. In this study, the underlying cloud scheduling structures and their taxonomies (differently analysing compile-time static allocation in contrast with run-time dynamic allocation, independent batch of tasks vs. dependency-based scientific workflows) are explored and multidimensional performance assessment parameters are analysed. In particular, the emphasis is put on QoS provisions, Service Level Agreements, execution cost, makespan, and resource utilization in the cluster. Besides that, operational issues in distributed virtualization platforms are also considered. Among others, these are the complex latency and throughput overheads resulting from runtime VM live migration such as the iterative dirty-memory pre-copying process, secondary storage disk I/O overheads, and uninterrupted network connectivity, along with the critical challenges in multi-tenancy environment, that is, the threat of unapproved VM hopping, noisy neighbour VM's resource poaching behavior, and divergence in cloning configurations on shared network infrastructure. This paper attempts to solve the ongoing conflict between end-user's requirement of deadline guarantee and the provider's requirement of resource optimization through introducing the theoretical and mathematical formulation of a new framework referred to as Deadline-Based VM Optimization (DBVO). DBVO combines dynamic slack-time analysis with earliest completion time metrics to emphasize time-critical tasks, achieve system-wide load balancing, avoid schedule bottlenecks, and SLA violation fines. Moreover, an experimental roadmap to test performance of this new method using CloudSim simulator is outlined.