Information and communication infrastructure provides the backbone of today's networked economy. The fact that service development and provisioning has become highly automated brings down operating costs and facilitates many new business models that were impossible only a few years ago. New technological developments have led to substantial changes in the way how this infrastructure is being provided. The shift to cloud computing and virtualization is arguably the most influential development in IT service management. Infrastructure-as-a-Service (IaaS) providers account for an important part of the cloud service market, hosting virtual machines (VMs) for their customers, but there is no dedicated allocation to a physical server anymore. Live migration allows to move VMs from one server to another during runtime seamlessly.
The consideration of demand complementarities in the demand patterns of VMs allows for a significant reduction in the number of active servers and an increase in the energy efficiency of data centers. Such exogenously given demand patterns lead to new, very high-dimensional bin-packing and scheduling problems, which have received little attention in the literature so far.
Moreover, the order and type of VMs requested by the customers is typically unknown and demands for algorithms that cope with incomplete information. Standard competitive analysis, which evaluates the performance of an online algorithm under an adversarial worst-case arrival sequence, may be too pessimistic and does not always lead to meaningful results. Recent research on an alternative, random-order model has produced significant results---for maximization problems. Minimization problems, such as minimizing cost, loads or waiting times when allocating resources in data centers, appear technically much more challenging since "wrong'' decisions cannot be neglected when appearing with bounded probability but may cause severely increased cost. Thus, different techniques and analytical methods are needed. Moreover, data centers often possess additional distributional information about the VM request sequence which demands for dynamic stochastic scheduling policies tailored to the specific requirements of data centers.