Infrastructure as a Service (IaaS) providers currently have no knowledge of the time frame customers intend to lease resources. However, scheduling in the absence of lease time information leads to wasted resources in times of decreasing demand. We explore how IaaS providers can use lease times to optimize resource allocation. We present two virtual machine scheduling algorithms to optimize the virtual-to-physical machine mapping taking lease time into account. Through simulation with synthetic and real-world workloads we evaluate the algorithms' potential to reduce the number of powered-up physical machines. Depending on data center size and request distribution the cumulative machine uptime is reduced by 28.4% to 51.5% when compared to round robin scheduling and by 3.3% to 16.7% when compared to first fit. Using a real-world workload from Google we achieve savings of 36.7% and 9.9% compared against round robin and first fit, respectively.