1. A computer-implemented method for updating an application executing on a programmable execution service (“PES”), the method comprising executing instructions on one or more computers for: receiving update preferences specifying one or more factors for use in applying one or more updates to an application executing on a PES, wherein the PES comprises a plurality of computing systems, wherein the application executes on a plurality of virtual machine instances executing on the computer systems, each of the virtual machine instances being an instance of a software implementation of a machine, and wherein the one or more factors comprise economic factors, temporal factors, and operational factors, the economic factors indicating the extent to which additional costs are to be incurred for instantiating new virtual machine instances during deployment of the update, and the temporal factors indicating the extent to which time is a factor in deploying the update; utilizing the factors specified in the update preferences to generate a deployment plan that specifies how the one or more updates are to be applied to the application including whether one or more new virtual machine instances in the PES are permitted to be created and utilized to deploy the one or more updates; and deploying the one or more updates to the application executing on the plurality of virtual machine instances according to the deployment plan.