Techniques are described for managing execution of programs. In some situations, program execution is managed for multiple users using excess program execution capacity of one or more computing systems. In some such situations, excess or otherwise unused program execution capacity may be made available to execute programs on a temporary basis, such that the programs executing using the excess program execution capacity may be terminated at any time if other preferred use for the excess program execution capacity arises. The excess program execution capacity may in some situations be provided in conjunction with other dedicated program execution capacity that is allocated to particular users, such as to use unused dedicated capacity of some users as excess capacity for other users. In some situations, the techniques are used in conjunction with a fee-based program execution service that executes multiple programs on behalf of multiple users of the service.