1. A computer-implemented method for de-scaling virtual machine instances utilized to implement a programmable execution service (“PES”) application, the method comprising performing computer-implemented operations for: determining that one or more of the virtual machine instances are to be terminated following an application of an update to the PES application based on a deployment plan, wherein the deployment plan specifies that the virtual machine instances are to be terminated according to a utilized percentage of a paid-for time period; responsive to the determination that one or more of the virtual machine instances are to be terminated, determining the utilized percentage of the paid-for time period used by each of the virtual machine instances based on data maintained by a PES platform indicating how much of each paid-for time period has been used by each of the virtual machine instances, wherein the paid-for time period of a particular virtual machine instance is a period of time which a customer pays for to use the particular virtual machine instance; and responsive to the determination of the utilized percentage, terminating at least one of the virtual machine instances that have used the greatest percentage of the paid-for time period.