Techniques are described for performing automated predictions of program execution capacity or other capacity of computing-related hardware resources that will be used to execute software programs in the future, such as for a group of computing nodes that execute one or more programs for a user. The predictions that are performed may in at least some situations be based on historical data regarding corresponding prior actual usage of execution-related capacity (e.g., for one or more prior years), and may include long-term predictions for particular future time periods that are multiple months or years into the future. In addition, the predictions of the execution-related capacity for particular future time periods may be used in various manners, including to manage execution-related capacity at or before those future time periods, such as to prepare sufficient execution-related capacity to be available at those future time periods.