  Cloud computing environments often have to deal with random-arrival
computational workloads that vary in resource requirements and demand high
Quality of Service (QoS) obligations. It is typical that a
Service-Level-Agreement (SLA) is employed to govern the QoS obligations of the
cloud computing service provider to the client. A typical challenge
service-providers face every day is maintaining a balance between the limited
resources available for computing and the high QoS requirements of varying
random demands. Any imbalance in managing these conflicting objectives may
result in either dissatisfied clients and potentially significant commercial
penalties, or an over-resourced cloud computing environment that can be
significantly costly to acquire and operate. Thus, scheduling the clients'
workloads as they arrive at the environment to ensure their timely execution
has been a central issue in cloud computing. Various approaches have been
reported in the literature to address this problem: Shortest-Queue,
Join-Idle-Queue, Round Robin, MinMin, MaxMin, and Least Connection, to name a
few. However, optimization strategies of such approaches fail to capture QoS
obligations and their associated commercial penalties. This paper presents an
approach for service-level driven load scheduling and balancing in multi-tier
environments. Joint scheduling and balancing operations are employed to
distribute and schedule jobs among the resources, such that the total waiting
time of client jobs is minimized, and thus the potential of a penalty to be
incurred by the service provider is mitigated. A penalty model is used to
quantify the penalty the service provider incurs as a function of the jobs'
total waiting time. A Virtual-Queue abstraction is proposed to facilitate
optimal job scheduling at the tier level. This problem is NP-complete, a
genetic algorithm is proposed for computing job schedules.
