Virtual machines provide a promising vehicle for controlled sharing of physical resources, allowing us to instantiate a precisely defined virtual resource, configured with desired software configuration and hardware properties, on a set of physical resources. We describe a model of virtual machine provisioning in a Grid environment that allows us to define such virtual resources and efficiently instantiate them on a physical Grid infrastructure. We argue that to properly account for, and manage, the overhead resulting from instantiating and managing virtual resources, overhead must be scheduled at the same level as virtual resources, instead of being deducted from a user’s resource allocation. We present preliminary results that demonstrate the benefits of such an approach.